Amnon Ta-Shma
Office: CheckPoint 245
Tel: 03-6405364,
Fax: 03-6409357.
Email: first name at tauex dot tau dot ac dot
il.
Papers:
·
Gil Cohen, Dean Doron, Ori
Sberlo and Amnon Ta-Shma. Approximating Iterated Multiplication of Stochastic
Matrices in Small Space. STOC 2023
·
Itay Kalev and Amnon Ta-Shma.
Unbalanced Expanders from Multiplicity Code. Random 2022
·
Dan Karliner and Amnon Ta-Shma.
Improved Local testing for multiplicity codes.
Random
2022
·
Dan Karliner, Roie Salama and
Amnon Ta-Shma. The plane test is a local tester for Multiplicity Codes, CCC 2022
·
Gil Cohen, Dean Doron, Oren
Renard, Ori Sberlo and Amnon Ta-Shma. Error Reduction For
Weighted PRGs Against Read Once Branching Programs. CCC 2021
·
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin and Amnon Ta-Shma. Expander Random
Walks: The general case and limitations. ICALP 2022
·
Gil Cohen, Noam Peri and Amnon
Ta-Shma. Expander Random Walks: A Fourier-analytic Approach. STOC 2021
·
Avraham Ben-Aroya, Dean Doron
and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. CCC 2020
·
Dean Doron, Amnon Ta-Shma and
Roei Tell. On Hitting-Set Generators for Polynomials that Vanish Rarely. Random 2020 CC22.
·
Avraham Ben-Aroya, Gil Cohen,
Dean Doron and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small
Entropy Gap via Entropy-Resilient Functions. Random 2019
·
Irit Dinur, Prahladh Harsha,
Tali Kaufmann, Inbal Livni and Amnon Ta-Shma. List Decoding with Double
Samplers. SODA 2019 SICOMP 2021
·
Nir Aviv and Amnon Ta-Shma. On
the entropy loss and gap of condensers. ToCT 2018
·
Avraham Ben-Aroya, Eshan
Chattopadhyay, Dean Doron, Xin Li and Amnon Ta- Shma.
A New Approach for Constructing Low-Error, Two-Source Extractors. CCC 2018
·
Amnon Ta-Shma. Explicit,
almost optimal, epsilon-balanced codes. STOC 2017.
·
Avraham Ben-Aroya, Dean Doron
and Amnon Ta-Shma. An efficient reduction from non-malleable extractors to
two-source extractors, and explicit two-source extractors with near-logarithmic
min-entropy. STOC
2017 SICOMP
2022.
·
Dean Doron, Francois Le Gall
and Amnon Ta-Shma. Probabilistic logarithmic-space algorithms for Laplacian
solvers. Random
2017.
·
Dean Doron, Amir Sarid and Amnon Ta-Shma. On Approximating the Eigenvalues
of Stochastic Matrices in Probabilistic Logspace. Computational
Complexity 2017
·
Dean Doron and Amnon Ta-Shma.
On the de-randomization of space-bounded approximate counting problems. IPL 2015
·
Dean Doron, Amnon Ta-Shma. On
the Problem of Approximating the Eigenvalues of Undirected Graphs in
Probabilistic Logspace. ICALP 2015
·
Efraim Gelman and Amnon
Ta-Shma. The Benes network is q(q-1)/2n almost q-set-wise independent. FSTTCS14
·
Gil Cohen and Amnon Ta-Shma.
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry
Codes. ECCC 2013
·
Idan Dershowitz, Nachum
Dershowitz, Tomer Hasid and Amnon Ta-Shma. Orthography and Biblical Criticism. Digital Humainities
(DH) 2104 Poster (in
DH’14)Amnon Ta-Shma.
QCrypt 2013 Tutorial. Extractors against classical and quantum adversaries. Slides Video
·
Amnon Ta-Shma. Inverting well conditioned matrices in Quantum Logspace.
STOC 2013
Video
(Cambridge 2013)
·
Rotem Arnon-Friedman,
Esther Hanggi and Amnon Ta-shma.
Towards the impossibility of non-signalling privacy
amplification from time-like ordering constraints. Quant-ph
·
Rotem Arnon-Friedman
and Amnon Ta-Shma. Limits of privacy amplification against non-signalling memory attacks. Quant-ph
Phys-Rev-A 2012
QCrypt2013: Extended abstract
Slides Video
·
Jonathan Ben-Nun, Niko Farhi,
Morgan Llewellyn, Ben Riva, Alon Rosen and Amnon Ta-Shma. A new implementation of
a dual (paper and cryptographic) voting system. EVOTE 2012.
·
Amnon Ta-Shma and Chris Umans. Better condensers and new extractors from Parvaresh-Vardy codes. CC 2011
PPT .
·
Avi Ben-Aroya, Amnon Ta-Shma.
Better short seed quantum-proof extractors. Quant-ph
TCS 2012
·
Avi Ben-Aroya, Klim Efremenk, Amnon Ta-Shma. A
note on amplifying the error tolerance of locally decodable codes. ECCC 2010
·
Avi Ben-Aroya, Klim Efremenk, Amnon Ta-Shma.
Local list decoding with a constant number of queries. FOCS 2010
·
Avi Ben-Aroya, Amnon Ta-Shma.
Constructing Small-Bias Sets from Algebraic-Geometric Codes. FOCS 2009 ToC 2013
·
Avi Ben-Aroya, Amnon Ta-Shma.
On the complexity of approximating the diamond norm. QIC 2010
·
Avi Ben-Aroya, Amnon Ta-Shma.
Approximate quantum error correction for correlated noise. IEEE IT 2011 QIP09 SLIDES
·
Amnon Ta-Shma. Short seed
extractors against quantum storage. Quant-ph
STOC
2009 SICOMP
2011 QIP09
SLIDES
·
Avi Ben-Aroya, Amnon Ta-Shma.
A combinatorial construction of almost-Ramanujan graphs using the zig-zag
product. STOC
2008 SICOMP 2011 SLIDES
·
Avi Ben-Aroya, Oded Schwarts, Amnon Ta-Shma. Quantum expanders: motivation and
construction. CCC
2008 TOC 2010.
Includes material from:
Avi Ben-Aroya, Oded
Schwarts, Amnon Ta-Shma. An explicit construction of
quantum expanders. Quant-ph
Avi Ben-Aroya,
Amnon Ta-Shma. Quantum expanders and the quantum entropy difference problem. Quant-ph
·
Alex Rapaport, Amnon Ta-Shma.
On the power of quantum, one round, two prover interactive proof systems. Quant-ph
QIP 2007.
·
Dan Gutfreund, Amnon Ta-Shma.
Worst-case to average-case reductions revisited. Random 2007
ECCC 2006
·
Ben Riva, Amnon Ta-Shma.
Bare-Handed electronic voting with pre-processing. Wote 2007
Evt 2007
·
Amnon Ta-Shma, Uri Zwick.
Deterministic rendezvous, treasure hunts and strongly universal exploration
sequences. SODA
2007 TALG 2013
SLIDES
·
Ishay Haviv, Oded Regev, Amnon Ta-Shma. On the hardness of satisfiabilty with bounded occurrences in the polynomial
time hierarchy. TOC 2007
·
Chris Umans,
Amnon Ta-Shma. Better lossless condensers through derandomized curve samplers. FOCS 2006
·
Ronen Gradwohl,
Guy Kindler, Omer Reingold, Amnon Ta-Shma. On the error parameter of
dispersers. Random
2005
·
Dan Gutfreund, Ronen Shaltiel,
Amnon Ta-Shma. If NP languages are hard on the worst-case then it is easy to
find their hard instances. CCC-05 CC 2007
SLIDES
·
Eran Rom, Amnon Ta-Shma.
Improving the alphabet-size in high noise, almost optimal rate list decodable
codes. STACS-05
Eran's thesis
IEEE trans on
information thy-06
·
Tal Moran, Ronen Shaltiel,
Amnon Ta-Shma. Passive Timestamping in the Bounded Storage Model. CRYPTO-04
J-Cryptology
2009
·
Ron Berman, Amos Fiat, Amnon
Ta-Shma. Provable Unlinkability Against Traffic
Analysis. FC04
Long version
SLIDES
·
Dan Gutfreund, Ronen Shaltiel,
Amnon Ta-Shma. Uniform Hardness vs. Randomness Tradeoffs for Arthur Merlin
Games. CC 2003
Computational
Complexity 2003
·
Dorit Aharonov, Amnon Ta-Shma. Adiabatic Quantum State Generation
and Statistical Zero Knowledge. Quant-ph 2003
STOC 2003
SICOMP 2007
·
Orna Kupferman, Amnon Ta-shma, Moshe Vardi. Concurrency Counts. Draft
·
Amnon Ta-Shma. Storing
information with extractors. IPL 2002
·
Amnon Ta-Shma, David
Zuckerman, Shmuel Safra. Extractors from Reed-Muller
codes. FOCS 2001
JCSS 2006
·
Amnon Ta-Shma, Christopher Umans, David Zuckerman. Loss-less condensers, unbalanced
expanders and extractor. STOC 2001
Combinatorica 2007
·
Amnon Ta-Shma, David
Zuckerman. Extractor codes. STOC 2001
IEEE IT
·
Hartmut Klauck, Ashwin Nayak,
Amnon Ta-Shma, David Zuckerman. Interaction in quantum communication and the
complexity of set disjointness. STOC 2001
IEEE IT
·
Sean Hallgren,
Alexander Russell, Amnon Ta-Shma. Normal Subgroup Reconstruction and Quantum
Computation Using Group Representations. STOC 2000
SIAM J. on
Computing 2002
·
Dorit Aharonov, Amnon Ta-Shma, Umesh Vazirani, Andrew C. Yao.
Quantum Bit Escrow. STOC 2000
·
Tomas Sander, Amnon Ta-Shma,
Moti Yung. Blind, Auditable Membership Proof. Financial
Cryptography 2000
·
Amnon Ta-Shma. Classical versus
Quantum Communication Complexity. SIGACT News,
Complexity Theory Column 23, 1999
·
Tomas Sander, Amnon Ta-Shma.
On Anonymous Electronic Cash and Crime. ISW 1999
·
Tomas Sander, Amnon Ta-Shma.
Auditable, Anonymous Electronic Cash. Crypto 1999
·
Andris Ambainis,
Ashwin Nayak, Amnon Ta-Shma, Umesh Vazirani. Dense Quantum Coding and a Lower
Bound on 1-way Quantum Finite Automata. STOC 1999
JACM 2000
·
Tomas Sander, Amnon Ta-Shma.
Flow control: A New Approach for Anonymity Control in Electronic Cash Systems. Financial Cryptography
1999
·
Andris Ambainis,
Leonid Schulman, Amnon Ta-Shma, Umesh Vazirani, Avi Wigderson. The Quantum
Communication Complexity of Sampling. FOCS 1998
SIAM Journal
on Computing 2003
·
Amnon Ta-Shma. Almost Optimal
dispersers. STOC
1998 Combinatorica
2002
·
Jaikumar Radhakrishnan, Amnon
Ta-Shma. Tight bounds for depth-two superconcentrators.
FOCS 1997
SIAM Journal on
Discrete Mathematics 2000
·
Roy Armoni,
Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou. SL is in L^{4/3}. STOC 1997 JACM 2000
·
Noam Nisan, Amnon Ta-Shma.
Extracting Randomness: A Survey and New Constructions. JCSS 1999
·
My Thesis:
Refining Randomness. Hebrew University
1996
·
Amnon Ta-Shma. On Extracting
Randomness From Weak Random Sources. STOC 1996
·
Amnon Ta-Shma. A Note On PCP
vs. MIP. IPL 1996
·
Noam Nisan, Amnon Ta-Shma.
Symmetric Logspace is Closed Under Complement. STOC 1995 Chicago Journal of
Theoretical Computer Science 1995