Amnon Ta-Shma

School of computer science

Tel-Aviv University

 

Office: CheckPoint 245

Tel: 03-6405364,

Fax: 03-6409357.

Email: first name at tauex dot tau dot ac dot il.

 

Classes

Students

 

Papers:

 

·        Amnon Ta-Shma and Zadicario. The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. Random 2024

 

·        Itay Cohen, Roy Roth and Amnon Ta-Shma. HDX Condensers. FOCS 2023

 

·       Gil Cohen, Dean Doron, Ori Sberlo and Amnon Ta-Shma. Approximating Iterated Multiplication of Stochastic Matrices in Small Space. STOC 2023

 

·       Itay Kalev and Amnon Ta-Shma. Unbalanced Expanders from Multiplicity Code. Random 2022

 

·       Dan Karliner and Amnon Ta-Shma. Improved Local testing for multiplicity codes.  Random 2022

 

·       Dan Karliner, Roie Salama and Amnon Ta-Shma. The plane test is a local tester for Multiplicity Codes, CCC 2022

 

·       Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo and Amnon Ta-Shma. Error Reduction For Weighted PRGs Against Read Once Branching Programs. CCC 2021

 

·       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