Amnon Ta-Shma

School of computer science

Tel-Aviv University

Office: Schrieber 127

Tel: 03-6405364,

Fax: 03-6409357.

Email: first name at tau dot ac dot il.

Classes

Students

Papers:

· Irit Dinur, Prahladh Harsha, Tali Kaufmann, Inbal Livni and Amnon Ta-Shma. List Decoding with Double Samplers.
Accepted to SODA 2019
. 


· Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li and Amnon Ta- Shma. 
A New Approach for Constructing Low-Error, Two-Source Extractors. Accepted to 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.

· 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