| 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 |
| https://portal.mardi4nfdi.de/entity/Q6126316 | 2024-04-09 | Paper |
| The work of Mark Braverman | 2024-03-22 | Paper |
| Parallel repetition for all 3-player games over binary alphabet | 2023-12-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6070396 | 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 |
| https://portal.mardi4nfdi.de/entity/Q6062142 | 2023-10-31 | Paper |
| Oracle Separation of BQP and PH | 2023-04-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875714 | 2023-02-03 | Paper |
| Quantum versus randomized communication complexity, with efficient players | 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 | 2022-03-31 | Paper |
| A lower bound for adaptively-secure collective coin flipping protocols | 2021-09-22 | Paper |
| Exponential Separation of Communication and External Information | 2021-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4993274 | 2021-06-15 | Paper |
| Oracle separation of BQP and PH | 2020-01-30 | Paper |
| Extractor-based time-space lower bounds for learning | 2019-08-22 | Paper |
| Fast Learning Requires Good Memory | 2019-02-25 | Paper |
| Label Cover Instances with Large Girth and the Hardness of Approximating Basic k -Spanner | 2018-10-30 | Paper |
| Exponential Separation of Information and Communication for Boolean Functions | 2018-08-02 | Paper |
| Exponential separation of communication and external information | 2017-09-29 | Paper |
| Time-space hardness of learning sparse parities | 2017-08-17 | Paper |
| Competing provers protocols for circuit evaluation | 2017-05-16 | Paper |
| Two Sides of the Coin Problem | 2017-03-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2969656 | 2017-03-22 | Paper |
| Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound | 2017-02-15 | Paper |
| Bounds on locally testable codes with unique tests | 2016-10-07 | Paper |
| Exponential separation of quantum and classical communication complexity | 2016-09-29 | Paper |
| On recycling the randomness of states in space bounded computation | 2016-09-29 | Paper |
| PCP characterizations of NP: towards a polynomially-small error-probability | 2016-09-29 | Paper |
| Extracting all the randomness and reducing the error in Trevisan's extractors | 2016-09-29 | Paper |
| Bounds on 2-query locally testable codes with affine tests | 2016-05-10 | Paper |
| On the space complexity of linear programming with preprocessing | 2016-04-15 | Paper |
| Multi-linear formulas for permanent and determinant are of super-polynomial size | 2015-11-11 | Paper |
| Exponential Separation of Information and Communication for Boolean Functions | 2015-08-21 | Paper |
| Resolution lower bounds for the weak pigeonhole principle | 2015-08-01 | Paper |
| How to delegate computations | 2015-06-26 | Paper |
| Arthur-Merlin streaming complexity | 2015-06-09 | Paper |
| Lower bounds for matrix product, in bounded depth circuits with arbitrary gates | 2015-02-27 | Paper |
| Explicit lower bound of 4.5n - o(n) for boolena circuits | 2015-02-27 | Paper |
| Regular resolution lower bounds for the weak pigeonhole principle | 2015-02-27 | Paper |
| Sub-constant error low degree test of almost-linear size | 2014-11-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191608 | 2014-10-06 | Paper |
| Higher lower bounds on monotone size | 2014-09-26 | Paper |
| Pseudorandom Generators for Regular Branching Programs | 2014-09-18 | Paper |
| Tensor-rank and lower bounds for arithmetic formulas | 2014-08-13 | Paper |
| Average-case lower bounds for formula size | 2014-08-07 | Paper |
| Interactive channel capacity | 2014-08-07 | Paper |
| Delegation for bounded space | 2014-08-07 | Paper |
| Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification | 2014-07-30 | Paper |
| Tensor-Rank and Lower Bounds for Arithmetic Formulas | 2014-02-17 | Paper |
| Efficient multiparty protocols via log-depth threshold formulae. (Extended abstract) | 2013-09-17 | Paper |
| Label cover instances with large girth and the hardness of approximating basic \(k\)-spanner | 2013-08-12 | Paper |
| Arthur-Merlin streaming complexity | 2013-08-06 | Paper |
| PCP characterizations of NP: toward a polynomially-small error-probability | 2011-11-30 | Paper |
| A counterexample to strong parallel repetition | 2011-10-18 | Paper |
| Memory delegation | 2011-08-12 | Paper |
| The surprise examination paradox and the second incompleteness theorem | 2011-07-04 | Paper |
| Separation of multilinear circuit and formula size | 2011-05-24 | Paper |
| Elusive functions and lower bounds for arithmetic circuits | 2011-05-24 | Paper |
| Lower bounds and separations for constant depth multilinear circuits | 2011-02-18 | Paper |
| Sub-constant error probabilistically checkable proof of almost-linear size | 2011-02-18 | Paper |
| Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors | 2011-01-18 | Paper |
| Extractors with weak random seeds | 2010-08-16 | Paper |
| Multi-linear formulas for permanent and determinant are of super-polynomial size | 2010-08-15 | Paper |
| Two-query PCP with subconstant error | 2010-08-09 | Paper |
| Resolution lower bounds for the weak pigeonhole principle | 2010-08-05 | Paper |
| On the complexity of matrix product | 2010-08-05 | Paper |
| Balancing syntactically multilinear arithmetic circuits | 2010-03-15 | Paper |
| Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography | 2009-11-06 | Paper |
| Strong Parallel Repetition Theorem for Free Projection Games | 2009-10-28 | Paper |
| Probabilistically Checkable Arguments | 2009-10-20 | Paper |
| Quantum information and the PCP theorem | 2009-08-31 | Paper |
| A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits | 2009-08-20 | Paper |
| Deterministic extractors for affine sources over large fields | 2009-07-20 | Paper |
| The strength of multilinear proofs | 2009-06-17 | Paper |
| Sub-Constant Error Low Degree Test of Almost-Linear Size | 2009-03-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5302096 | 2009-01-05 | Paper |
| Resolution over linear equations and multilinear proofs | 2008-11-12 | Paper |
| Interactive PCP | 2008-08-19 | Paper |
| Analyzing linear mergers | 2008-06-05 | Paper |
| Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed | 2007-09-07 | Paper |
| A time lower bound for satisfiability | 2006-01-09 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2005-08-25 | Paper |
| Automata, Languages and Programming | 2005-08-24 | Paper |
| Regular resolution lower bounds for the weak pigeonhole principle | 2005-07-05 | Paper |
| Deterministic polynomial identity testing in non-commutative models | 2005-06-16 | Paper |
| Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles | 2005-02-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650570 | 2005-02-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4650569 | 2005-02-18 | Paper |
| Distance labeling in graphs | 2004-11-12 | Paper |
| Approximating CVP to within almost-polynomial factors is NP-hard | 2004-09-07 | Paper |
| On the distribution of the number of roots of polynomials and explicit weak designs | 2003-10-22 | Paper |
| On the Complexity of Matrix Product | 2003-09-28 | Paper |
| Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates | 2003-06-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4549235 | 2003-06-16 | Paper |
| Extracting all the randomness and reducing the error in Trevisan's extractors | 2003-05-04 | Paper |
| Distance labeling in graphs (extended abstract) | 2002-03-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234093 | 2002-01-30 | Paper |
| The BNS-Chung criterion for multi-party communication complexity | 2001-04-17 | Paper |
| VC-dimension of sets of permutations | 2001-04-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527015 | 2001-02-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4527004 | 2001-02-28 | Paper |
| Arthur-Merlin games in Boolean decision trees | 2000-11-22 | Paper |
| On Interpolation and Automatization for Frege Systems | 2000-10-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4258571 | 2000-10-17 | Paper |
| Separation of the monotone NC hierarchy | 2000-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4936140 | 2000-01-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234107 | 1999-09-07 | Paper |
| Lower bounds on the distortion of embedding finite metric spaces in graphs | 1998-06-22 | Paper |
| A Parallel Repetition Theorem | 1998-05-10 | Paper |
| Lower bounds for cutting planes proofs with small coefficients | 1998-02-02 | Paper |
| Fourier analysis for probabilistic communication complexity | 1996-11-10 | Paper |
| Super-logarithmic depth lower bounds via the direct sum in communication complexity | 1996-11-10 | Paper |
| On the ``log rank-conjecture in communication complexity | 1996-09-15 | Paper |
| Monotone circuits for matching require linear depth | 1994-08-21 | Paper |
