Amnon Ta-Shma

ORCID

Publication Activity (10 Years)

Years Active: 1994-2023
Publications (10 Years): 45

Top Venues

Electron. Colloquium Comput. Complex.

STOC

APPROX-RANDOM

Computational Complexity Conference

Publications

Itay Cohen, Roy Roth, Amnon Ta-Shma
HDX Condensers. FOCS (2023)
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
Approximating Iterated Multiplication of Stochastic Matrices in Small Space. STOC (2023)
Itay Cohen, Roy Roth, Amnon Ta-Shma
HDX Condensers. Electron. Colloquium Comput. Complex. (2023)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy. SIAM J. Comput. 51 (2) (2022)
Itay Kalev, Amnon Ta-Shma
Unbalanced Expanders from Multiplicity Codes. Electron. Colloquium Comput. Complex. (2022)
Dan Karliner, Amnon Ta-Shma
Improved local testing for multiplicity codes. Electron. Colloquium Comput. Complex. (2022)
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
Approximating Iterated Multiplication of Stochastic Matrices in Small Space. Electron. Colloquium Comput. Complex. (2022)
Dan Karliner, Roie Salama, Amnon Ta-Shma
The plane test is a local tester for Multiplicity Codes. Electron. Colloquium Comput. Complex. 29 (2022)
Itay Kalev, Amnon Ta-Shma
Unbalanced Expanders from Multiplicity Codes. APPROX/RANDOM (2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
Expander Random Walks: The General Case and Limitations. ICALP (2022)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials that Vanish Rarely. Comput. Complex. 31 (2) (2022)
Dan Karliner, Amnon Ta-Shma
Improved Local Testing for Multiplicity Codes. APPROX/RANDOM (2022)
Dan Karliner, Roie Salama, Amnon Ta-Shma
The Plane Test Is a Local Tester for Multiplicity Codes. CCC (2022)
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma
Error Reduction for Weighted PRGs Against Read Once Branching Programs. Computational Complexity Conference (2021)
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
List-Decoding with Double Samplers. SIAM J. Comput. 50 (2) (2021)
Gil Cohen, Noam Peri, Amnon Ta-Shma
Expander random walks: a Fourier-analytic approach. STOC (2021)
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma
Error Reduction For Weighted PRGs Against Read Once Branching Programs. Electron. Colloquium Comput. Complex. 28 (2021)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
Expander Random Walks: The General Case and Limitations. Electron. Colloquium Comput. Complex. 28 (2021)
Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma
Pr-ZSUBEXP is not contained in Pr-RP. Electron. Colloquium Comput. Complex. 27 (2020)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials That Vanish Rarely. APPROX-RANDOM (2020)
Gil Cohen, Noam Peri, Amnon Ta-Shma
Expander Random Walks: A Fourier-Analytic Approach. Electron. Colloquium Comput. Complex. 27 (2020)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Near-Optimal Erasure List-Decodable Codes. Computational Complexity Conference (2020)
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. APPROX-RANDOM (2019)
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
List Decoding with Double Samplers. SODA (2019)
Nir Aviv, Amnon Ta-Shma
On the Entropy Loss and Gap of Condensers. ACM Trans. Comput. Theory 11 (3) (2019)
Dean Doron, Amnon Ta-Shma, Roei Tell
On Hitting-Set Generators for Polynomials that Vanish Rarely. Electron. Colloquium Comput. Complex. 26 (2019)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends. Electron. Colloquium Comput. Complex. 25 (2018)
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
List Decoding with Double Samplers. CoRR (2018)
Ishay Haviv, Oded Regev, Amnon Ta-Shma
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy. CoRR (2018)
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
A New Approach for Constructing Low-Error, Two-Source Extractors. Computational Complexity Conference (2018)
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. Electron. Colloquium Comput. Complex. 25 (2018)
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
List Decoding with Double Samplers. Electron. Colloquium Comput. Complex. 25 (2018)
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate. Electron. Colloquium Comput. Complex. 24 (2017)
Amnon Ta-Shma
Explicit, almost optimal, epsilon-balanced codes. STOC (2017)
Dean Doron, Amir Sarid, Amnon Ta-Shma
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace. Comput. Complex. 26 (2) (2017)
Amnon Ta-Shma
Explicit, almost optimal, epsilon-balanced codes. Electron. Colloquium Comput. Complex. 24 (2017)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy. STOC (2017)
Dean Doron, François Le Gall, Amnon Ta-Shma
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers. APPROX-RANDOM (2017)
Dean Doron, Francois Le Gall, Amnon Ta-Shma
Probabilistic logarithmic-space algorithms for Laplacian solvers. Electron. Colloquium Comput. Complex. 24 (2017)
Dean Doron, Amir Sarid, Amnon Ta-Shma
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Electron. Colloquium Comput. Complex. 23 (2016)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Explicit two-source extractors for near-logarithmic min-entropy. Electron. Colloquium Comput. Complex. 23 (2016)
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
Low-error two-source extractors for polynomial min-entropy. Electron. Colloquium Comput. Complex. 23 (2016)
Dean Doron, Amnon Ta-Shma
On the de-randomization of space-bounded approximate counting problems. Inf. Process. Lett. 115 (10) (2015)
Ron Berman, Amos Fiat, Marcin Gomulkiewicz, Marek Klonowski, Miroslaw Kutylowski, Tomer Levinboim, Amnon Ta-Shma
Provable Unlinkability Against Traffic Analysis with Low Message Overhead. J. Cryptol. 28 (3) (2015)
Dean Doron, Amnon Ta-Shma
On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace. ICALP (1) (2015)
Idan Dershowitz, Nachum Dershowitz, Tomer Hasid, Amnon Ta-Shma
Orthography and Biblical Criticism. DH (2014)
Amnon Ta-Shma, Uri Zwick
Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences. ACM Trans. Algorithms 10 (3) (2014)
Efraim Gelman, Amnon Ta-Shma
The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent. FSTTCS (2014)
Gil Cohen, Amnon Ta-Shma
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes. Electron. Colloquium Comput. Complex. 20 (2013)
Avraham Ben-Aroya, Amnon Ta-Shma
Constructing Small-Bias Sets from Algebraic-Geometric Codes. Theory Comput. 9 (2013)
Amnon Ta-Shma
Inverting well conditioned matrices in quantum logspace. STOC (2013)
Jonathan Ben-Nun, Niko Fahri, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon Ta-Shma, Douglas Wikström
A New Implementation of a Dual (Paper and Cryptographic) Voting System. Electronic Voting (2012)
Amnon Ta-Shma, Christopher Umans
Better Condensers and New Extractors from Parvaresh-Vardy Codes. Computational Complexity Conference (2012)
Rotem Arnon Friedman, Esther Hänggi, Amnon Ta-Shma
Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints CoRR (2012)
Rotem Arnon Friedman, Amnon Ta-Shma
On the limits of privacy amplification against non-signalling memory attacks CoRR (2012)
Avraham Ben-Aroya, Amnon Ta-Shma
Better short-seed quantum-proof extractors. Theor. Comput. Sci. 419 (2012)
Avraham Ben-Aroya, Amnon Ta-Shma
Approximate Quantum Error Correction for Correlated Noise. IEEE Trans. Inf. Theory 57 (6) (2011)
Avraham Ben-Aroya, Amnon Ta-Shma
A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product. SIAM J. Comput. 40 (2) (2011)
Amnon Ta-Shma
Short Seed Extractors against Quantum Storage. SIAM J. Comput. 40 (3) (2011)
Avraham Ben-Aroya, Amnon Ta-Shma
On the complexity of approximating the diamond norm. Quantum Inf. Comput. 10 (1&2) (2010)
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
A Note on Amplifying the Error-Tolerance of Locally Decodable Codes. Electron. Colloquium Comput. Complex. 17 (2010)
Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma
Quantum Expanders: Motivation and Construction. Theory Comput. 6 (1) (2010)
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Local List Decoding with a Constant Number of Queries. FOCS (2010)
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
Local list decoding with a constant number of queries. Electron. Colloquium Comput. Complex. 17 (2010)
Avraham Ben-Aroya, Amnon Ta-Shma
Constructing Small-Bias Sets from Algebraic-Geometric Codes. FOCS (2009)
Amnon Ta-Shma
Short seed extractors against quantum storage. STOC (2009)
Tal Moran, Ronen Shaltiel, Amnon Ta-Shma
Non-interactive Timestamping in the Bounded-Storage Model. J. Cryptol. 22 (2) (2009)
Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma
Quantum Expanders: Motivation and Constructions. Computational Complexity Conference (2008)
Avraham Ben-Aroya, Amnon Ta-Shma
A combinatorial construction of almost-ramanujan graphs using the zig-zag product. STOC (2008)
Ishay Haviv, Oded Regev, Amnon Ta-Shma
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy. Theory Comput. 3 (1) (2007)
Alex Rapaport, Amnon Ta-Shma
On the Power of Quantum, One Round, Two Prover Interactive Proof Systems. Quantum Inf. Process. 6 (6) (2007)
Dan Gutfreund, Amnon Ta-Shma
Worst-Case to Average-Case Reductions Revisited. APPROX-RANDOM (2007)
Amnon Ta-Shma, Uri Zwick
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. SODA (2007)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Interaction in Quantum Communication. IEEE Trans. Inf. Theory 53 (6) (2007)
Ben Riva, Amnon Ta-Shma
Bare-Handed Electronic Voting with Pre-processing. EVT (2007)
Amnon Ta-Shma, Christopher Umans, David Zuckerman
Lossless Condensers, Unbalanced Expanders, And Extractors. Comb. 27 (2) (2007)
Dorit Aharonov, Amnon Ta-Shma
Adiabatic Quantum State Generation. SIAM J. Comput. 37 (1) (2007)
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. Comput. Complex. 16 (4) (2007)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Extractors from Reed-Muller codes. J. Comput. Syst. Sci. 72 (5) (2006)
Eran Rom, Amnon Ta-Shma
Improving the Alphabet-Size in Expander-Based Code Constructions. IEEE Trans. Inf. Theory 52 (8) (2006)
Amnon Ta-Shma, Christopher Umans
Better lossless condensers through derandomized curve samplers. FOCS (2006)
Dan Gutfreund, Amnon Ta-Shma
New connections between derandomization, worst-case complexity and average-case complexity. Electron. Colloquium Comput. Complex. 13 (108) (2006)
Eran Rom, Amnon Ta-Shma
Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes. STACS (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. Computational Complexity Conference (2005)
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
On the Error Parameter of Dispersers. APPROX-RANDOM (2005)
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
On the Error Parameter of Dispersers Electron. Colloquium Comput. Complex. (061) (2005)
Amnon Ta-Shma, David Zuckerman
Extractor codes. IEEE Trans. Inf. Theory 50 (12) (2004)
Eran Rom, Amnon Ta-Shma
Improveing the alphabet size in high noise, almost optimal rate list decodable codes Electron. Colloquium Comput. Complex. (069) (2004)
Tal Moran, Ronen Shaltiel, Amnon Ta-Shma
Non-interactive Timestamping in the Bounded Storage Model. CRYPTO (2004)
Ron Berman, Amos Fiat, Amnon Ta-Shma
Provable Unlinkability against Traffic Analysis. Financial Cryptography (2004)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32 (6) (2003)
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. Computational Complexity Conference (2003)
Dorit Aharonov, Amnon Ta-Shma
Adiabatic quantum state generation and statistical zero knowledge. STOC (2003)
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
The Hidden Subgroup Problem and Quantum Computation Using Group Representations. SIAM J. Comput. 32 (4) (2003)
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Comput. Complex. 12 (3-4) (2003)
Amnon Ta-Shma
Almost Optimal Dispersers. Comb. 22 (1) (2002)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense quantum coding and quantum finite automata. J. ACM 49 (4) (2002)
Amnon Ta-Shma
Storing information with extractors. Inf. Process. Lett. 83 (5) (2002)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
Interaction in quantum communication and the complexity of set disjointness. STOC (2001)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Extractors from Reed-Muller Codes. FOCS (2001)

Amnon Ta-Shma.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Amnon Ta-Shma