| Publication | Date of Publication | Type |
|---|
Is untrusted randomness helpful?
| 2024-09-25 | Paper |
Polynomial bounds on parallel repetition for all 3-player games with binary inputs
| 2024-08-22 | Paper |
Quantum logspace computations are verifiable
| 2024-05-29 | Paper |
Memory-sample lower bounds for learning with classical-quantum hybrid memory
| 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829308 (Why is no real title available?)
| 2024-04-09 | Paper |
The work of Mark Braverman
International Congress of Mathematicians | 2024-03-22 | Paper |
Parallel repetition for all 3-player games over binary alphabet
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
scientific article; zbMATH DE number 7768397 (Why is no real title available?)
| 2023-11-20 | Paper |
Parallel Repetition for the GHZ Game: A Simpler Proof.
| 2023-11-20 | Paper |
Memory-Sample Lower Bounds for Learning Parity with Noise
| 2023-11-20 | Paper |
scientific article; zbMATH DE number 7758323 (Why is no real title available?)
| 2023-10-31 | Paper |
Oracle Separation of BQP and PH
Journal of the ACM | 2023-04-27 | Paper |
scientific article; zbMATH DE number 7650368 (Why is no real title available?)
| 2023-02-03 | Paper |
Quantum versus randomized communication complexity, with efficient players
Computational Complexity | 2022-11-24 | Paper |
Time-space lower bounds for two-pass learning
| 2022-07-27 | Paper |
A lower bound for adaptively-secure collective coin-flipping protocols
| 2022-07-21 | Paper |
How to Delegate Computations: The Power of No-Signaling Proofs
Journal of the ACM | 2022-03-31 | Paper |
A lower bound for adaptively-secure collective coin flipping protocols
Combinatorica | 2021-09-22 | Paper |
Exponential separation of communication and external information
SIAM Journal on Computing | 2021-06-29 | Paper |
A candidate for a strong separation of information and communication
| 2021-06-15 | Paper |
Oracle separation of BQP and PH
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Extractor-based time-space lower bounds for learning
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Fast learning requires good memory: a time-space lower bound for parity learning
Journal of the ACM | 2019-02-25 | Paper |
Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Exponential separation of information and communication for Boolean functions
Journal of the ACM | 2018-08-02 | Paper |
Exponential separation of communication and external information
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Time-space hardness of learning sparse parities
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Competing provers protocols for circuit evaluation
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Two sides of the coin problem
| 2017-03-22 | Paper |
Space pseudorandom generators by communication complexity lower bounds
| 2017-03-22 | Paper |
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
SIAM Journal on Computing | 2017-02-15 | Paper |
Bounds on locally testable codes with unique tests
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Exponential separation of quantum and classical communication complexity
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
On recycling the randomness of states in space bounded computation
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
PCP characterizations of NP: towards a polynomially-small error-probability
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Extracting all the randomness and reducing the error in Trevisan's extractors
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Bounds on 2-query locally testable codes with affine tests
Information Processing Letters | 2016-05-10 | Paper |
On the space complexity of linear programming with preprocessing
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Multi-linear formulas for permanent and determinant are of super-polynomial size
Journal of the ACM | 2015-11-11 | Paper |
Exponential Separation of Information and Communication for Boolean Functions
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Resolution lower bounds for the weak pigeonhole principle
Journal of the ACM | 2015-08-01 | Paper |
How to delegate computations
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Arthur-Merlin streaming complexity
Information and Computation | 2015-06-09 | Paper |
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Explicit lower bound of 4.5n - o(n) for boolena circuits
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Regular resolution lower bounds for the weak pigeonhole principle
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Sub-constant error low degree test of almost-linear size
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Competing-provers protocols for circuit evaluation
Theory of Computing | 2014-10-06 | Paper |
Higher lower bounds on monotone size
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Pseudorandom generators for regular branching programs
SIAM Journal on Computing | 2014-09-18 | Paper |
Tensor-rank and lower bounds for arithmetic formulas
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Average-case lower bounds for formula size
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Interactive channel capacity
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Delegation for bounded space
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Nonmalleable extractors with short seeds and applications to privacy amplification
SIAM Journal on Computing | 2014-07-30 | Paper |
Tensor-rank and lower bounds for arithmetic formulas
Journal of the ACM | 2014-02-17 | Paper |
Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract)
Advances in Cryptology – CRYPTO 2013 | 2013-09-17 | Paper |
Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner
Automata, Languages, and Programming | 2013-08-12 | Paper |
Arthur-Merlin streaming complexity
Automata, Languages, and Programming | 2013-08-06 | Paper |
PCP characterizations of NP: toward a polynomially-small error-probability
Computational Complexity | 2011-11-30 | Paper |
A counterexample to strong parallel repetition
SIAM Journal on Computing | 2011-10-18 | Paper |
Memory delegation
Advances in Cryptology – CRYPTO 2011 | 2011-08-12 | Paper |
The surprise examination paradox and the second incompleteness theorem
| 2011-07-04 | Paper |
Separation of multilinear circuit and formula size
Theory of Computing | 2011-05-24 | Paper |
Elusive functions and lower bounds for arithmetic circuits
Theory of Computing | 2011-05-24 | Paper |
Lower bounds and separations for constant depth multilinear circuits
Computational Complexity | 2011-02-18 | Paper |
Sub-constant error probabilistically checkable proof of almost-linear size
Computational Complexity | 2011-02-18 | Paper |
Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Extractors with weak random seeds
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Multi-linear formulas for permanent and determinant are of super-polynomial size
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Two-query PCP with subconstant error
Journal of the ACM | 2010-08-09 | Paper |
Resolution lower bounds for the weak pigeonhole principle
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
On the complexity of matrix product
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Balancing syntactically multilinear arithmetic circuits
Computational Complexity | 2010-03-15 | Paper |
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
SIAM Journal on Computing | 2009-11-06 | Paper |
Strong Parallel Repetition Theorem for Free Projection Games
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Probabilistically Checkable Arguments
Advances in Cryptology - CRYPTO 2009 | 2009-10-20 | Paper |
Quantum information and the PCP theorem
Algorithmica | 2009-08-31 | Paper |
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
SIAM Journal on Computing | 2009-08-20 | Paper |
Deterministic extractors for affine sources over large fields
Combinatorica | 2009-07-20 | Paper |
The strength of multilinear proofs
Computational Complexity | 2009-06-17 | Paper |
Sub-Constant Error Low Degree Test of Almost-Linear Size
SIAM Journal on Computing | 2009-03-16 | Paper |
scientific article; zbMATH DE number 5485585 (Why is no real title available?)
| 2009-01-05 | Paper |
Resolution over linear equations and multilinear proofs
Annals of Pure and Applied Logic | 2008-11-12 | Paper |
Interactive PCP
Automata, Languages and Programming | 2008-08-19 | Paper |
Analyzing linear mergers
Random Structures \& Algorithms | 2008-06-05 | Paper |
Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
SIAM Journal on Computing | 2007-09-07 | Paper |
A time lower bound for satisfiability
Theoretical Computer Science | 2006-01-09 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Regular resolution lower bounds for the weak pigeonhole principle
Combinatorica | 2005-07-05 | Paper |
Deterministic polynomial identity testing in non-commutative models
Computational Complexity | 2005-06-16 | Paper |
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
SIAM Journal on Computing | 2005-02-21 | Paper |
scientific article; zbMATH DE number 2134904 (Why is no real title available?)
| 2005-02-18 | Paper |
scientific article; zbMATH DE number 2134903 (Why is no real title available?)
| 2005-02-18 | Paper |
Distance labeling in graphs
Journal of Algorithms | 2004-11-12 | Paper |
Approximating CVP to within almost-polynomial factors is NP-hard
Combinatorica | 2004-09-07 | Paper |
On the distribution of the number of roots of polynomials and explicit weak designs
Random Structures \& Algorithms | 2003-10-22 | Paper |
On the Complexity of Matrix Product
SIAM Journal on Computing | 2003-09-28 | Paper |
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
SIAM Journal on Computing | 2003-06-19 | Paper |
scientific article; zbMATH DE number 1789924 (Why is no real title available?)
| 2003-06-16 | Paper |
Extracting all the randomness and reducing the error in Trevisan's extractors
Journal of Computer and System Sciences | 2003-05-04 | Paper |
Distance labeling in graphs (extended abstract)
| 2002-03-14 | Paper |
scientific article; zbMATH DE number 1263221 (Why is no real title available?)
| 2002-01-30 | Paper |
The BNS-Chung criterion for multi-party communication complexity
Computational Complexity | 2001-04-17 | Paper |
VC-dimension of sets of permutations
Combinatorica | 2001-04-01 | Paper |
scientific article; zbMATH DE number 1559563 (Why is no real title available?)
| 2001-02-28 | Paper |
scientific article; zbMATH DE number 1559552 (Why is no real title available?)
| 2001-02-28 | Paper |
Arthur-Merlin games in Boolean decision trees
Journal of Computer and System Sciences | 2000-11-22 | Paper |
On Interpolation and Automatization for Frege Systems
SIAM Journal on Computing | 2000-10-18 | Paper |
scientific article; zbMATH DE number 1335880 (Why is no real title available?)
| 2000-10-17 | Paper |
Separation of the monotone NC hierarchy
Combinatorica | 2000-05-14 | Paper |
scientific article; zbMATH DE number 1392301 (Why is no real title available?)
| 2000-01-25 | Paper |
scientific article; zbMATH DE number 1263234 (Why is no real title available?)
| 1999-09-07 | Paper |
Lower bounds on the distortion of embedding finite metric spaces in graphs
Discrete \& Computational Geometry | 1998-06-22 | Paper |
A Parallel Repetition Theorem
SIAM Journal on Computing | 1998-05-10 | Paper |
Lower bounds for cutting planes proofs with small coefficients
Journal of Symbolic Logic | 1998-02-02 | Paper |
Fourier analysis for probabilistic communication complexity
Computational Complexity | 1996-11-10 | Paper |
Super-logarithmic depth lower bounds via the direct sum in communication complexity
Computational Complexity | 1996-11-10 | Paper |
On the ``log rank-conjecture in communication complexity
Combinatorica | 1996-09-15 | Paper |
Monotone circuits for matching require linear depth
Journal of the ACM | 1994-08-21 | Paper |
