Amnon
Ta-Shma
Office: Schrieber 127
Tel: 03-6405364,
Fax: 03-6409357.
Email: first name at tau dot ac dot il.
Papers:
Avi Ben-Aroya, Amnon Ta-Shma. Constructing Small-Bias Sets from Algebraic-Geometric Codes. FOCS 2009
Avi Ben-Aroya, Amnon Ta-Shma. On the complexity of approximating the diamond norm. QIC 2009
Avi Ben-Aroya, Amnon Ta-Shma. Approximate quantum error correction for correlated noise. Tex QIP09 SLIDES
Amnon Ta-Shma. Short seed extractors against quantum storage. Quant-ph QIP09 SLIDES
Avi Ben-Aroya, Amnon Ta-Shma. A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. STOC 2008 Long version SLIDES
Avi Ben-Aroya, Oded Schwarts, Amnon Ta-Shma. Quantum expanders: motivation and construction. CCC 2008 Long version
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 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
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