Amnon Ta-Shma

According to our database, Amnon Ta-Shma authored at least 93 papers between 1995 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

HDX Condensers.

Itay Cohen, Roy Roth, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2023

2022

An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

SIAM J. Comput., 2022

Improved local testing for multiplicity codes.

Dan Karliner, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2022

The plane test is a local tester for Multiplicity Codes.

Dan Karliner, Roie Salama, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2022

Unbalanced Expanders from Multiplicity Codes.

Itay Kalev, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2022

Approximating Iterated Multiplication of Stochastic Matrices in Small Space.

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2022

On Hitting-Set Generators for Polynomials that Vanish Rarely.

Dean Doron, Amnon Ta-Shma, Roei Tell

Comput. Complex., 2022

2021

Expander Random Walks: The General Case and Limitations.

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2021

Error Reduction For Weighted PRGs Against Read Once Branching Programs.

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2021

2020

Pr-ZSUBEXP is not contained in Pr-RP.

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2020

Expander Random Walks: A Fourier-Analytic Approach.

Gil Cohen, Noam Peri, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2020

Near-Optimal Erasure List-Decodable Codes.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Proceedings of the 35th Computational Complexity Conference, 2020

2019

On the Entropy Loss and Gap of Condensers.

Nir Aviv, Amnon Ta-Shma

ACM Trans. Comput. Theory, 2019

2018

List Decoding with Double Samplers.

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2018

Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2018

Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions.

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2018

A New Approach for Constructing Low-Error, Two-Source Extractors.

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Explicit, almost optimal, epsilon-balanced codes.

Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2017

Probabilistic logarithmic-space algorithms for Laplacian solvers.

Dean Doron, Francois Le Gall, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2017

A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate.

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2017

On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace.

Dean Doron, Amir Sarid, Amnon Ta-Shma

Comput. Complex., 2017

An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Low-error two-source extractors for polynomial min-entropy.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2016

Explicit two-source extractors for near-logarithmic min-entropy.

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2016

2015

Provable Unlinkability Against Traffic Analysis with Low Message Overhead.

Ron Berman, Amos Fiat, Marcin Gomulkiewicz, Marek Klonowski, Miroslaw Kutylowski, Tomer Levinboim, Amnon Ta-Shma

J. Cryptol., 2015

On the de-randomization of space-bounded approximate counting problems.

Dean Doron, Amnon Ta-Shma

Inf. Process. Lett., 2015

On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace.

Dean Doron, Amnon Ta-Shma

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences.

Amnon Ta-Shma, Uri Zwick

ACM Trans. Algorithms, 2014

The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent.

Efraim Gelman, Amnon Ta-Shma

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Orthography and Biblical Criticism.

Idan Dershowitz, Nachum Dershowitz, Tomer Hasid, Amnon Ta-Shma

Proceedings of the 9th Annual International Conference of the Alliance of Digital Humanities Organizations, 2014

2013

Constructing Small-Bias Sets from Algebraic-Geometric Codes.

Avraham Ben-Aroya, Amnon Ta-Shma

Theory Comput., 2013

Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes.

Gil Cohen, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2013

Inverting well conditioned matrices in quantum logspace.

Amnon Ta-Shma

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Better short-seed quantum-proof extractors.

Avraham Ben-Aroya, Amnon Ta-Shma

Theor. Comput. Sci., 2012

On the limits of privacy amplification against non-signalling memory attacks

Rotem Arnon Friedman, Amnon Ta-Shma

CoRR, 2012

Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints

Rotem Arnon Friedman, Esther Hänggi, Amnon Ta-Shma

CoRR, 2012

A New Implementation of a Dual (Paper and Cryptographic) Voting System.

Jonathan Ben-Nun, Niko Fahri, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon Ta-Shma, Douglas Wikström

Proceedings of the 5th International Conference on Electronic Voting 2012, 2012

Better Condensers and New Extractors from Parvaresh-Vardy Codes.

Amnon Ta-Shma, Christopher Umans

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Approximate Quantum Error Correction for Correlated Noise.

Avraham Ben-Aroya, Amnon Ta-Shma

IEEE Trans. Inf. Theory, 2011

Short Seed Extractors against Quantum Storage.

Amnon Ta-Shma

SIAM J. Comput., 2011

A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product.

Avraham Ben-Aroya, Amnon Ta-Shma

SIAM J. Comput., 2011

2010

Quantum Expanders: Motivation and Construction.

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma

Theory Comput., 2010

On the complexity of approximating the diamond norm.

Avraham Ben-Aroya, Amnon Ta-Shma

Quantum Inf. Comput., 2010

A Note on Amplifying the Error-Tolerance of Locally Decodable Codes.

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2010

Local list decoding with a constant number of queries.

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2010

2009

Non-interactive Timestamping in the Bounded-Storage Model.

Tal Moran, Ronen Shaltiel, Amnon Ta-Shma

J. Cryptol., 2009

2008

Quantum Expanders: Motivation and Constructions.

Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.

Ishay Haviv, Oded Regev, Amnon Ta-Shma

Theory Comput., 2007

Interaction in Quantum Communication.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

IEEE Trans. Inf. Theory, 2007

Adiabatic Quantum State Generation.

Dorit Aharonov, Amnon Ta-Shma

SIAM J. Comput., 2007

On the Power of Quantum, One Round, Two Prover Interactive Proof Systems.

Alex Rapaport, Amnon Ta-Shma

Quantum Inf. Process., 2007

Lossless Condensers, Unbalanced Expanders, And Extractors.

Amnon Ta-Shma, Christopher Umans, David Zuckerman

Comb., 2007

If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances.

Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma

Comput. Complex., 2007

Bare-Handed Electronic Voting with Pre-processing.

Ben Riva, Amnon Ta-Shma

Proceedings of the 2007 USENIX/ACCURATE Electronic Voting Technology Workshop, 2007

Worst-Case to Average-Case Reductions Revisited.

Dan Gutfreund, Amnon Ta-Shma

Proceedings of the Approximation, 2007

2006

Improving the Alphabet-Size in Expander-Based Code Constructions.

Eran Rom, Amnon Ta-Shma

IEEE Trans. Inf. Theory, 2006

Extractors from Reed-Muller codes.

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

J. Comput. Syst. Sci., 2006

New connections between derandomization, worst-case complexity and average-case complexity.

Dan Gutfreund, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2006

Better lossless condensers through derandomized curve samplers.

Amnon Ta-Shma, Christopher Umans

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

On the Error Parameter of Dispersers

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2005

Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes.

Eran Rom, Amnon Ta-Shma

Proceedings of the STACS 2005, 2005

2004

Extractor codes.

Amnon Ta-Shma, David Zuckerman

IEEE Trans. Inf. Theory, 2004

Improveing the alphabet size in high noise, almost optimal rate list decodable codes

Eran Rom, Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 2004

Provable Unlinkability against Traffic Analysis.

Ron Berman, Amos Fiat, Amnon Ta-Shma

Proceedings of the Financial Cryptography, 2004

2003

The Hidden Subgroup Problem and Quantum Computation Using Group Representations.

Sean Hallgren, Alexander Russell, Amnon Ta-Shma

SIAM J. Comput., 2003

The Quantum Communication Complexity of Sampling.

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson

SIAM J. Comput., 2003

Uniform hardness versus randomness tradeoffs for Arthur-Merlin games.

Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma

Comput. Complex., 2003

Adiabatic quantum state generation and statistical zero knowledge.

Dorit Aharonov, Amnon Ta-Shma

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games.

Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Dense quantum coding and quantum finite automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

J. ACM, 2002

Storing information with extractors.

Amnon Ta-Shma

Inf. Process. Lett., 2002

Almost Optimal Dispersers.

Amnon Ta-Shma

Comb., 2002

2001

Loss-less condensers, unbalanced expanders, and extractors.

Amnon Ta-Shma, Christopher Umans, David Zuckerman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Interaction in quantum communication and the complexity of set disjointness.

Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.

Jaikumar Radhakrishnan, Amnon Ta-Shma

SIAM J. Discret. Math., 2000

An <i>O</i>(log(<i>n</i>)^4/3) space algorithm for (<i>s, t</i>) connectivity in undirected graphs.

Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou

J. ACM, 2000

Interaction in Quantum Communication Complexity

Ashwin Nayak, Amnon Ta-Shma, David Zuckerman

CoRR, 2000

Normal subgroup reconstruction and quantum computation using group representations.

Sean Hallgren, Alexander Russell, Amnon Ta-Shma

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Quantum bit escrow.

Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Blind, Auditable Membership Proofs.

Tomas Sander, Amnon Ta-Shma, Moti Yung

Proceedings of the Financial Cryptography, 2000

1999

Classical versus quantum communication complexity.

Amnon Ta-Shma

SIGACT News, 1999

Extracting Randomness: A Survey and New Constructions.

Noam Nisan, Amnon Ta-Shma

J. Comput. Syst. Sci., 1999

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On Anonymous Electronic Cash and Crime.

Tomas Sander, Amnon Ta-Shma

Proceedings of the Information Security, Second International Workshop, 1999

Flow Control: A New Approach for Anonymity Control in Electronic Cash Systems.

Tomas Sander, Amnon Ta-Shma

Proceedings of the Financial Cryptography, 1999

Auditable, Anonymous Electronic Cash Extended Abstract.

Tomas Sander, Amnon Ta-Shma

Proceedings of the Advances in Cryptology, 1999

1997

SL <= L^4/3.

Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Tight Bounds for Depth-two Superconcentrators.

Jaikumar Radhakrishnan, Amnon Ta-Shma

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

Refining randomness (כיצד לזקק אקראיות גסה.).

Amnon Ta-Shma

PhD thesis, 1996

A Note on PCP vs. MIP.

Amnon Ta-Shma

Inf. Process. Lett., 1996

On Extracting Randomness From Weak Random Sources (Extended Abstract).

Amnon Ta-Shma

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

On Extracting Randomness From Weak Random Sources

Amnon Ta-Shma

Electron. Colloquium Comput. Complex., 1995

Symmetric Logspace is Closed Under Complement.

Noam Nisan, Amnon Ta-Shma

Chic. J. Theor. Comput. Sci., 1995