Amnon Ta-Shma
Office: Schrieber 127
Tel:
03-6405364,
Fax:
03-6409357.
Email:
first name at tau dot ac dot il.
Papers:
·
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
·
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
2011
·
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 Long version
·
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 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