| Publication | Date of Publication | Type |
|---|
| Quantum and classical strong direct product theorems and optimal time-space tradeoffs | 2026-05-29 | Paper |
| Quantum algorithms for matrix scaling and matrix balancing | 2026-05-12 | Paper |
| Private quantum channels | 2026-05-08 | Paper |
| Bounds for small-error and zero-error quantum algorithms | 2026-05-06 | Paper |
| Quantum lower bounds by polynomials | 2025-10-29 | Paper |
| Quantum speedup for graph sparsification, cut approximation and Laplacian solving | 2025-08-12 | Paper |
| Exponential separation between quantum communication and logarithm of approximate rank | 2025-08-12 | Paper |
| Quantum SDP-solvers: better upper and lower bounds | 2025-08-06 | Paper |
| Tight bounds for the randomized and quantum communication complexities of equality with small error | 2025-07-28 | Paper |
| Improved quantum boosting | 2025-01-06 | Paper |
| Tight bounds for quantum phase estimation and related problems | 2025-01-06 | Paper |
| Quantum algorithms and lower bounds for linear regression with norm constraints | 2024-11-14 | Paper |
| Influence in completely bounded block-multilinear forms and classical simulation of quantum algorithms | 2024-07-05 | Paper |
| Symmetry and quantum query-to-communication simulation | 2024-04-23 | Paper |
| Avi Wigderson's work and influence | 2024-04-08 | Paper |
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
SIAM Journal on Computing | 2023-04-04 | Paper |
scientific article; zbMATH DE number 7651037 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
| Improved Bounds on Fourier Entropy and Min-Entropy | 2023-02-07 | Paper |
Two new results about quantum exact learning
(available as arXiv preprint) | 2022-07-21 | Paper |
Improved bounds on Fourier entropy and min-entropy
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
Improved bounds on Fourier entropy and min-entropy
ACM Transactions on Computation Theory | 2022-03-29 | Paper |
| Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms | 2022-02-28 | Paper |
Optimal quantum sample complexity of learning algorithms
(available as arXiv preprint) | 2020-05-26 | Paper |
| Optimal quantum sample complexity of learning algorithms | 2019-01-30 | Paper |
Efficient quantum algorithms for (gapped) group testing and junta testing
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Attacks on the AJPS Mersenne based cryptosystem | 2018-06-22 | Paper |
Optimal parallel quantum query algorithms
Algorithmica | 2017-10-10 | Paper |
On the sum-of-squares degree of symmetric quadratic functions
(available as arXiv preprint) | 2017-10-10 | Paper |
Some upper and lower bounds on PSD-rank
Mathematical Programming. Series A. Series B | 2017-03-23 | Paper |
Fooling one-sided quantum protocols
(available as arXiv preprint) | 2017-01-30 | Paper |
Optimal quantum query bounds for almost all Boolean functions
(available as arXiv preprint) | 2017-01-30 | Paper |
New bounds on the classical and quantum communication complexity of some graph properties
(available as arXiv preprint) | 2017-01-26 | Paper |
Exponential lower bounds for polytopes in combinatorial optimization
Journal of the ACM | 2016-03-24 | Paper |
Exponential lower bounds for polytopes in combinatorial optimization
Journal of the ACM | 2016-03-24 | Paper |
Query complexity in expectation
Automata, Languages, and Programming | 2015-10-27 | Paper |
How low can approximate degree and quantum query complexity be for total Boolean functions?
Computational Complexity | 2015-01-23 | Paper |
Bounded-error quantum state identification and exponential separations in communication complexity
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Optimal parallel quantum query algorithms
Lecture Notes in Computer Science | 2014-10-08 | Paper |
Near-optimal and explicit Bell inequality violations
Theory of Computing | 2014-10-06 | Paper |
Linear vs. semidefinite extended formulations
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
scientific article; zbMATH DE number 6292744 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 2014-05-07 | Paper |
Simultaneous communication protocols with quantum and classical messages
Chicago Journal of Theoretical Computer Science | 2014-05-06 | Paper |
Error-correcting data structures
SIAM Journal on Computing | 2013-07-04 | Paper |
| New results on quantum property testing | 2012-08-29 | Paper |
| Error-correcting data structures | 2012-04-24 | Paper |
| Locally decodable quantum codes | 2012-04-24 | Paper |
Locally decodable quantum codes
(available as arXiv preprint) | 2012-04-24 | Paper |
| Efficient and error-correcting data structures for membership and polynomial evaluation | 2012-01-23 | Paper |
Uniform approximation by (quantum) polynomials
(available as arXiv preprint) | 2011-10-05 | Paper |
| Upper bounds on the noise threshold for fault-tolerant quantum computing | 2011-10-05 | Paper |
Bell inequalities: what do we know about them and why should cryptographers care? (Invited talk)
Lecture Notes in Computer Science | 2011-05-19 | Paper |
Better Gap-Hamming Lower Bounds via Better Round Elimination
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Bounded-error quantum state identification and exponential separations in communication complexity
SIAM Journal on Computing | 2010-03-17 | Paper |
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
SIAM Journal on Computing | 2009-11-06 | Paper |
A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
Algorithmica | 2009-08-31 | Paper |
Quantum symmetrically-private information retrieval
Information Processing Letters | 2009-07-21 | Paper |
Quantum zero-error algorithms cannot be composed
Information Processing Letters | 2009-04-28 | Paper |
Lower Bounds on Matrix Rigidity Via a Quantum Argument
Automata, Languages and Programming | 2009-03-12 | Paper |
A note on quantum algorithms and the minimal degree of -error polynomials for symmetric functions
(available as arXiv preprint) | 2009-02-24 | Paper |
Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing
Automata, Languages and Programming | 2008-08-28 | Paper |
Quantum lower bounds by polynomials
Journal of the ACM | 2008-02-11 | Paper |
Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
SIAM Journal on Computing | 2007-10-22 | Paper |
Robust polynomials and quantum algorithms
Theory of Computing Systems | 2007-08-23 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Quantum Algorithms for Element Distinctness
SIAM Journal on Computing | 2005-09-16 | Paper |
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Journal of Computer and System Sciences | 2004-11-18 | Paper |
| scientific article; zbMATH DE number 2086394 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2086398 (Why is no real title available?) | 2004-08-11 | Paper |
| scientific article; zbMATH DE number 2038718 (Why is no real title available?) | 2004-02-08 | Paper |
Nondeterministic Quantum Query and Communication Complexities
SIAM Journal on Computing | 2003-06-19 | Paper |
Complexity measures and decision tree complexity: a survey.
Theoretical Computer Science | 2003-01-21 | Paper |
Quantum communication and complexity.
Theoretical Computer Science | 2003-01-21 | Paper |
A lower bound for quantum search of an ordered list
Information Processing Letters | 2002-07-25 | Paper |
Average-case quantum query complexity
Journal of Physics A: Mathematical and General | 2002-01-27 | Paper |
Marked PCP is decidable
Theoretical Computer Science | 2001-08-20 | Paper |
| scientific article; zbMATH DE number 1500513 (Why is no real title available?) | 2000-09-04 | Paper |
| scientific article; zbMATH DE number 1304321 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1149427 (Why is no real title available?) | 1998-05-11 | Paper |
Foundations of inductive logic programming
Lecture Notes in Computer Science | 1997-06-04 | Paper |
