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:

 

·         Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. STOC 2017 best paper award.

·         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