Amnon Ta-Shma
Office: CheckPoint 245
Tel: 03-6405364,
Fax: 03-6409357.
Email: first name at tauex dot tau dot ac dot
il.
Papers:
·
Itay Kalev and Amnon Ta-Shma.
Unbalanced Expanders from Multiplicity Code. Random 2022
·
Gil Cohen, Dor
Minzer, Shir Peleg, Aaron Potechin and Amnon Ta-Shma.
Expander Random Walks: The general case and limitations. ICALP 2022
·
Gil Cohen, Noam Peri and Amnon
Ta-Shma. Expander Random Walks: A Fourier-analytic Approach. STOC
2021
·
Avraham Ben-Aroya, Dean Doron
and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. CCC
2020
·
Dean Doron, Amnon Ta-Shma and Roei Tell. On
Hitting-Set Generators for Polynomials that Vanish Rarely. Random 2020 CC22.
·
Avraham Ben-Aroya, Gil Cohen,
Dean Doron and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small
Entropy Gap via Entropy-Resilient Functions. Random 2019
·
Irit Dinur, Prahladh Harsha, Tali Kaufmann, Inbal Livni and
Amnon Ta-Shma. List Decoding with Double Samplers. SODA 2019 SICOMP
2021
·
Nir Aviv and Amnon Ta-Shma. On
the entropy loss and gap of condensers. ToCT 2018
·
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean
Doron, Xin Li and Amnon Ta- Shma. A New Approach for
Constructing Low-Error, Two-Source Extractors. 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 SICOMP 2022.
·
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