Amnon Ta-Shma

134 papers A* 30A 14Journal 75Unranked 14
YearRankTypeTitle / Venue / Authors
2025 J jnl
Better Weighted Pseudorandom Generators Against Low Weight Read-Once Branching Programs.
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma, Ben Chen
2025 A conf
Simplifying Armoni's PRG.
APPROX/RANDOM
Ben Chen, Amnon Ta-Shma
2025 J jnl
Simplyfing Armoni's PRG.
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma, Ben Chen
2024 J jnl
Character sums over AG codes.
Electron. Colloquium Comput. Complex.
Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch
2024 A conf
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced.
APPROX/RANDOM
Amnon Ta-Shma, Ron Zadicario
2024 J jnl
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced.
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma, Ron Zadiario
2023 A ed.
38th Computational Complexity Conference, CCC 2023, Warwick, UK, July 17-20, 2023
CCC
Amnon Ta-Shma
2023 A* conf
Approximating Iterated Multiplication of Stochastic Matrices in Small Space.
STOC
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
2023 A* conf
HDX Condensers.
FOCS
Itay Cohen, Roy Roth, Amnon Ta-Shma
2023 J jnl
HDX Condensers.
Electron. Colloquium Comput. Complex.
Itay Cohen, Roy Roth, Amnon Ta-Shma
2022 J jnl
An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy.
SIAM J. Comput.
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2022 J jnl
Approximating Iterated Multiplication of Stochastic Matrices in Small Space.
Electron. Colloquium Comput. Complex.
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
2022 A* conf
Expander Random Walks: The General Case and Limitations.
ICALP
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
2022 A conf
Improved Local Testing for Multiplicity Codes.
APPROX/RANDOM
Dan Karliner, Amnon Ta-Shma
2022 J jnl
Improved local testing for multiplicity codes.
Electron. Colloquium Comput. Complex.
Dan Karliner, Amnon Ta-Shma
2022 J jnl
On Hitting-Set Generators for Polynomials that Vanish Rarely.
Comput. Complex.
Dean Doron, Amnon Ta-Shma, Roei Tell
2022 A conf
The Plane Test Is a Local Tester for Multiplicity Codes.
CCC
Dan Karliner, Roie Salama, Amnon Ta-Shma
2022 J jnl
The plane test is a local tester for Multiplicity Codes.
Electron. Colloquium Comput. Complex.
Dan Karliner, Roie Salama, Amnon Ta-Shma
2022 A conf
Unbalanced Expanders from Multiplicity Codes.
APPROX/RANDOM
Itay Kalev, Amnon Ta-Shma
2022 J jnl
Unbalanced Expanders from Multiplicity Codes.
Electron. Colloquium Comput. Complex.
Itay Kalev, Amnon Ta-Shma
2021 J jnl
Error Reduction For Weighted PRGs Against Read Once Branching Programs.
Electron. Colloquium Comput. Complex.
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma
2021 A conf
Error Reduction for Weighted PRGs Against Read Once Branching Programs.
CCC
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma
2021 J jnl
Expander Random Walks: The General Case and Limitations.
Electron. Colloquium Comput. Complex.
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma
2021 A* conf
Expander random walks: a Fourier-analytic approach.
STOC
Gil Cohen, Noam Peri, Amnon Ta-Shma
2021 J jnl
List-Decoding with Double Samplers.
SIAM J. Comput.
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
2020 J jnl
Expander Random Walks: A Fourier-Analytic Approach.
Electron. Colloquium Comput. Complex.
Gil Cohen, Noam Peri, Amnon Ta-Shma
2020 A conf
Near-Optimal Erasure List-Decodable Codes.
CCC
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2020 — conf
On Hitting-Set Generators for Polynomials That Vanish Rarely.
APPROX-RANDOM
Dean Doron, Amnon Ta-Shma, Roei Tell
2020 J jnl
Pr-ZSUBEXP is not contained in Pr-RP.
Electron. Colloquium Comput. Complex.
Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma
2019 A* conf
List Decoding with Double Samplers.
SODA
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
2019 J jnl
On Hitting-Set Generators for Polynomials that Vanish Rarely.
Electron. Colloquium Comput. Complex.
Dean Doron, Amnon Ta-Shma, Roei Tell
2019 J jnl
On the Entropy Loss and Gap of Condensers.
ACM Trans. Comput. Theory
Nir Aviv, Amnon Ta-Shma
2019 — conf
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions.
APPROX-RANDOM
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma
2018 A conf
A New Approach for Constructing Low-Error, Two-Source Extractors.
CCC
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
2018 J jnl
List Decoding with Double Samplers.
CoRR
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
2018 J jnl
List Decoding with Double Samplers.
Electron. Colloquium Comput. Complex.
Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma
2018 J jnl
Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2018 J jnl
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.
CoRR
Ishay Haviv, Oded Regev, Amnon Ta-Shma
2018 J jnl
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma
2017 J jnl
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
2017 A* conf
An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy.
STOC
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2017 A* conf
Explicit, almost optimal, epsilon-balanced codes.
STOC
Amnon Ta-Shma
2017 J jnl
Explicit, almost optimal, epsilon-balanced codes.
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma
2017 J jnl
On Approximating the Eigenvalues of Stochastic Matrices in Probabilistic Logspace.
Comput. Complex.
Dean Doron, Amir Sarid, Amnon Ta-Shma
2017 — conf
Probabilistic Logarithmic-Space Algorithms for Laplacian Solvers.
APPROX-RANDOM
Dean Doron, François Le Gall, Amnon Ta-Shma
2017 J jnl
Probabilistic logarithmic-space algorithms for Laplacian solvers.
Electron. Colloquium Comput. Complex.
Dean Doron, Francois Le Gall, Amnon Ta-Shma
2016 J jnl
Explicit two-source extractors for near-logarithmic min-entropy.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2016 J jnl
Low-error two-source extractors for polynomial min-entropy.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma
2016 J jnl
On approximating the eigenvalues of stochastic matrices in probabilistic logspace.
Electron. Colloquium Comput. Complex.
Dean Doron, Amir Sarid, Amnon Ta-Shma
2015 — conf
On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace.
ICALP (1)
Dean Doron, Amnon Ta-Shma
2015 J jnl
On the de-randomization of space-bounded approximate counting problems.
Inf. Process. Lett.
Dean Doron, Amnon Ta-Shma
2015 J jnl
Provable Unlinkability Against Traffic Analysis with Low Message Overhead.
J. Cryptol.
Ron Berman, Amos Fiat, Marcin Gomulkiewicz, Marek Klonowski, Miroslaw Kutylowski, Tomer Levinboim, Amnon Ta-Shma
2014 J jnl
Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences.
ACM Trans. Algorithms
Amnon Ta-Shma, Uri Zwick
2014 — conf
Orthography and Biblical Criticism.
DH
Idan Dershowitz, Nachum Dershowitz, Tomer Hasid, Amnon Ta-Shma
2014 — conf
The Benes Network is q*(q-1)/2n-Almost q-set-wise Independent.
FSTTCS
Efraim Gelman, Amnon Ta-Shma
2013 J jnl
Constructing Small-Bias Sets from Algebraic-Geometric Codes.
Theory Comput.
Avraham Ben-Aroya, Amnon Ta-Shma
2013 A* conf
Inverting well conditioned matrices in quantum logspace.
STOC
Amnon Ta-Shma
2013 J jnl
Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes.
Electron. Colloquium Comput. Complex.
Gil Cohen, Amnon Ta-Shma
2012 — conf
A New Implementation of a Dual (Paper and Cryptographic) Voting System.
Electronic Voting
Jonathan Ben-Nun, Niko Fahri, Morgan Llewellyn, Ben Riva, Alon Rosen, Amnon Ta-Shma, Douglas Wikström
2012 A conf
Better Condensers and New Extractors from Parvaresh-Vardy Codes.
CCC
Amnon Ta-Shma, Christopher Umans
2012 J jnl
Better short-seed quantum-proof extractors.
Theor. Comput. Sci.
Avraham Ben-Aroya, Amnon Ta-Shma
2012 J jnl
On the limits of privacy amplification against non-signalling memory attacks
CoRR
Rotem Arnon Friedman, Amnon Ta-Shma
2012 J jnl
Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints
CoRR
Rotem Arnon Friedman, Esther Hänggi, Amnon Ta-Shma
2011 J jnl
A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product.
SIAM J. Comput.
Avraham Ben-Aroya, Amnon Ta-Shma
2011 J jnl
Approximate Quantum Error Correction for Correlated Noise.
IEEE Trans. Inf. Theory
Avraham Ben-Aroya, Amnon Ta-Shma
2011 J jnl
Short Seed Extractors against Quantum Storage.
SIAM J. Comput.
Amnon Ta-Shma
2010 J jnl
A Note on Amplifying the Error-Tolerance of Locally Decodable Codes.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010 A* conf
Local List Decoding with a Constant Number of Queries.
FOCS
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010 J jnl
Local list decoding with a constant number of queries.
Electron. Colloquium Comput. Complex.
Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma
2010 J jnl
On the complexity of approximating the diamond norm.
Quantum Inf. Comput.
Avraham Ben-Aroya, Amnon Ta-Shma
2010 J jnl
Quantum Expanders: Motivation and Construction.
Theory Comput.
Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma
2009 A* conf
Constructing Small-Bias Sets from Algebraic-Geometric Codes.
FOCS
Avraham Ben-Aroya, Amnon Ta-Shma
2009 J jnl
Non-interactive Timestamping in the Bounded-Storage Model.
J. Cryptol.
Tal Moran, Ronen Shaltiel, Amnon Ta-Shma
2009 A* conf
Short seed extractors against quantum storage.
STOC
Amnon Ta-Shma
2008 A* conf
A combinatorial construction of almost-ramanujan graphs using the zig-zag product.
STOC
Avraham Ben-Aroya, Amnon Ta-Shma
2008 A conf
Quantum Expanders: Motivation and Constructions.
CCC
Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma
2007 J jnl
Adiabatic Quantum State Generation.
SIAM J. Comput.
Dorit Aharonov, Amnon Ta-Shma
2007 — conf
Bare-Handed Electronic Voting with Pre-processing.
EVT
Ben Riva, Amnon Ta-Shma
2007 A* conf
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences.
SODA
Amnon Ta-Shma, Uri Zwick
2007 J jnl
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances.
Comput. Complex.
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
2007 J jnl
Interaction in Quantum Communication.
IEEE Trans. Inf. Theory
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
2007 J jnl
Lossless Condensers, Unbalanced Expanders, And Extractors.
Comb.
Amnon Ta-Shma, Christopher Umans, David Zuckerman
2007 J jnl
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.
Theory Comput.
Ishay Haviv, Oded Regev, Amnon Ta-Shma
2007 J jnl
On the Power of Quantum, One Round, Two Prover Interactive Proof Systems.
Quantum Inf. Process.
Alex Rapaport, Amnon Ta-Shma
2007 — conf
Worst-Case to Average-Case Reductions Revisited.
APPROX-RANDOM
Dan Gutfreund, Amnon Ta-Shma
2006 A* conf
Better lossless condensers through derandomized curve samplers.
FOCS
Amnon Ta-Shma, Christopher Umans
2006 J jnl
Extractors from Reed-Muller codes.
J. Comput. Syst. Sci.
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2006 J jnl
Improving the Alphabet-Size in Expander-Based Code Constructions.
IEEE Trans. Inf. Theory
Eran Rom, Amnon Ta-Shma
2006 J jnl
New connections between derandomization, worst-case complexity and average-case complexity.
Electron. Colloquium Comput. Complex.
Dan Gutfreund, Amnon Ta-Shma
2005 A conf
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances.
CCC
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
2005 A conf
Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes.
STACS
Eran Rom, Amnon Ta-Shma
2005 J jnl
On the Error Parameter of Dispersers
Electron. Colloquium Comput. Complex.
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
2005 — conf
On the Error Parameter of Dispersers.
APPROX-RANDOM
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma
2004 J jnl
Extractor codes.
IEEE Trans. Inf. Theory
Amnon Ta-Shma, David Zuckerman
2004 J jnl
Improveing the alphabet size in high noise, almost optimal rate list decodable codes
Electron. Colloquium Comput. Complex.
Eran Rom, Amnon Ta-Shma
2004 A* conf
Non-interactive Timestamping in the Bounded Storage Model.
CRYPTO
Tal Moran, Ronen Shaltiel, Amnon Ta-Shma
2004 — conf
Provable Unlinkability against Traffic Analysis.
Financial Cryptography
Ron Berman, Amos Fiat, Amnon Ta-Shma
2003 A* conf
Adiabatic quantum state generation and statistical zero knowledge.
STOC
Dorit Aharonov, Amnon Ta-Shma
2003 J jnl
The Hidden Subgroup Problem and Quantum Computation Using Group Representations.
SIAM J. Comput.
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
2003 J jnl
The Quantum Communication Complexity of Sampling.
SIAM J. Comput.
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
2003 J jnl
Uniform hardness versus randomness tradeoffs for Arthur-Merlin games.
Comput. Complex.
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
2003 A conf
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games.
CCC
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma
2002 J jnl
Almost Optimal Dispersers.
Comb.
Amnon Ta-Shma
2002 J jnl
Dense quantum coding and quantum finite automata.
J. ACM
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
2002 J jnl
Storing information with extractors.
Inf. Process. Lett.
Amnon Ta-Shma
2001 A* conf
Extractor codes.
STOC
Amnon Ta-Shma, David Zuckerman
2001 J jnl
Extractors from Reed-Muller Codes
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2001 A* conf
Extractors from Reed-Muller Codes.
FOCS
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
2001 A* conf
Interaction in quantum communication and the complexity of set disjointness.
STOC
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
2001 A* conf
Loss-less condensers, unbalanced expanders, and extractors.
STOC
Amnon Ta-Shma, Christopher Umans, David Zuckerman
2000 J jnl
An
J. ACM
Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou
2000 — conf
Blind, Auditable Membership Proofs.
Financial Cryptography
Tomas Sander, Amnon Ta-Shma, Moti Yung
2000 J jnl
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators.
SIAM J. Discret. Math.
Jaikumar Radhakrishnan, Amnon Ta-Shma
2000 J jnl
Interaction in Quantum Communication Complexity
CoRR
Ashwin Nayak, Amnon Ta-Shma, David Zuckerman
2000 A* conf
Normal subgroup reconstruction and quantum computation using group representations.
STOC
Sean Hallgren, Alexander Russell, Amnon Ta-Shma
2000 A* conf
Quantum bit escrow.
STOC
Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao
1999 A* conf
Auditable, Anonymous Electronic Cash Extended Abstract.
CRYPTO
Tomas Sander, Amnon Ta-Shma
1999 J jnl
Classical versus quantum communication complexity.
SIGACT News
Amnon Ta-Shma
1999 A* conf
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
STOC
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
1999 J jnl
Extracting Randomness: A Survey and New Constructions.
J. Comput. Syst. Sci.
Noam Nisan, Amnon Ta-Shma
1999 — conf
Flow Control: A New Approach for Anonymity Control in Electronic Cash Systems.
Financial Cryptography
Tomas Sander, Amnon Ta-Shma
1999 — conf
On Anonymous Electronic Cash and Crime.
ISW
Tomas Sander, Amnon Ta-Shma
1998 A* conf
Almost Optimal Dispersers.
STOC
Amnon Ta-Shma
1998 J jnl
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata
CoRR
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
1998 A* conf
The Quantum Communication Complexity of Sampling.
FOCS
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
1997 A* conf
SL <= L
STOC
Roy Armoni, Amnon Ta-Shma, Avi Wigderson, Shiyu Zhou
1997 A* conf
Tight Bounds for Depth-two Superconcentrators.
FOCS
Jaikumar Radhakrishnan, Amnon Ta-Shma
1996 J jnl
A Note on PCP vs. MIP.
Inf. Process. Lett.
Amnon Ta-Shma
1996 A* conf
On Extracting Randomness From Weak Random Sources (Extended Abstract).
STOC
Amnon Ta-Shma
1996 — —
Refining randomness (כיצד לזקק אקראיות גסה.).
Amnon Ta-Shma
1995 J jnl
On Extracting Randomness From Weak Random Sources
Electron. Colloquium Comput. Complex.
Amnon Ta-Shma
1995 J jnl
Symmetric Logspace is Closed Under Complement.
Chic. J. Theor. Comput. Sci.
Noam Nisan, Amnon Ta-Shma
1995 A* conf
Symmetric logspace is closed under complement.
STOC
Noam Nisan, Amnon Ta-Shma
1994 J jnl
Symmetric Logspace is Closed Under Complement
Electron. Colloquium Comput. Complex.
Noam Nisan, Amnon Ta-Shma