Switzerland 2006 Part A 164Switzerland 2006 Part A 164Amnon 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.







         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

         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