| Publication | Date of Publication | Type |
|---|
| Hierarchy theorems for probabilistic polynomial time | 2026-05-29 | Paper |
| Testing that distributions are close | 2026-05-08 | Paper |
| Testing random variables for independence and identity | 2026-05-08 | Paper |
Challenges and opportunities in peer review
Notices of the American Mathematical Society | 2025-12-16 | Paper |
Resource-bounded Kolmogorov complexity revisited
Lecture Notes in Computer Science | 2022-11-09 | Paper |
| Computational complexity | 2022-04-28 | Paper |
| scientific article; zbMATH DE number 7075911 (Why is no real title available?) | 2019-07-03 | Paper |
| scientific article; zbMATH DE number 7015119 (Why is no real title available?) | 2019-02-07 | Paper |
Measure, category and learning theory
Automata, Languages and Programming | 2019-01-10 | Paper |
Results on resource-bounded measure
Automata, Languages and Programming | 2018-07-04 | Paper |
Resource-bounded instance complexity
STACS 95 | 2017-12-04 | Paper |
Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)
STACS 95 | 2017-12-04 | Paper |
| New non-uniform lower bounds for uniform classes | 2017-10-10 | Paper |
Robust simulations and significant separations
Information and Computation | 2017-09-28 | Paper |
| The Golden Ticket | 2017-07-20 | Paper |
Complexity with Rod
Computability and Complexity | 2017-04-04 | Paper |
Optimality and domination in repeated games with bounded players
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Time-space lower bounds for satisfiability
Journal of the ACM | 2015-12-04 | Paper |
Nondeterministic separations
Lecture Notes in Computer Science | 2015-09-30 | Paper |
Testing closeness of discrete distributions
Journal of the ACM | 2014-02-17 | Paper |
Learning Reductions to Sparse Sets
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
| The golden ticket. P, NP, and the search for the impossible | 2013-04-02 | Paper |
Inseparability and strong hypotheses for disjoint NP pairs
Theory of Computing Systems | 2012-12-07 | Paper |
Low-depth witnesses are easy to find
Computational Complexity | 2012-08-24 | Paper |
| Inseparability and strong hypotheses for disjoint NP pairs | 2012-01-23 | Paper |
Robust simulations and significant separations
Lecture Notes in Computer Science | 2011-07-06 | Paper |
Tolerant versus intolerant testing for Boolean properties
Theory of Computing | 2011-05-24 | Paper |
A simple proof of Toda's theorem
Theory of Computing | 2011-05-24 | Paper |
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Information and Computation | 2011-04-28 | Paper |
Complexity classes of equivalence problems revisited
Information and Computation | 2011-04-28 | Paper |
Infeasibility of instance compression and succinct PCPs for NP
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Gaming prediction markets: equilibrium strategies with a market maker
Algorithmica | 2010-11-08 | Paper |
Beyond NP
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Hierarchies for semantic classes
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Using depth to capture average-case complexity.
Lecture Notes in Computer Science | 2010-04-20 | Paper |
Does the polynomial hierarchy collapse if onto functions are invertible?
Theory of Computing Systems | 2010-03-05 | Paper |
Sophistication revisited
Theory of Computing Systems | 2009-09-18 | Paper |
| scientific article; zbMATH DE number 5604084 (Why is no real title available?) | 2009-09-15 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2009-08-07 | Paper |
Unconditional Lower Bounds against Advice
Automata, Languages and Programming | 2009-07-14 | Paper |
On the complexity of succinct zero-sum games
Computational Complexity | 2009-06-17 | Paper |
The Complexity of Forecast Testing
Econometrica | 2009-05-18 | Paper |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
Automata, Languages and Programming | 2009-03-12 | Paper |
Efficient learning algorithms yield circuit lower bounds
Journal of Computer and System Sciences | 2009-01-09 | Paper |
| scientific article; zbMATH DE number 5485524 (Why is no real title available?) | 2009-01-05 | Paper |
Quantum Property Testing
SIAM Journal on Computing | 2008-10-28 | Paper |
Inverting Onto Functions and Polynomial Hierarchy
Computer Science – Theory and Applications | 2008-06-03 | Paper |
Kolmogorov Complexity with Error
STACS 2006 | 2008-03-19 | Paper |
Linear Advice for Randomized Logarithmic Space
STACS 2006 | 2008-03-19 | Paper |
Proving SAT does not have small circuits with an application to the two queries problem
Journal of Computer and System Sciences | 2008-03-11 | Paper |
Efficient Learning Algorithms Yield Circuit Lower Bounds
Learning Theory | 2007-09-14 | Paper |
Very Sparse Leaf Languages
Lecture Notes in Computer Science | 2007-09-05 | Paper |
Infinitely‐Often Autoreducible Sets
SIAM Journal on Computing | 2007-06-26 | Paper |
Circuit lower bounds à la Kolmogorov
Information and Computation | 2006-10-10 | Paper |
A tight lower bound for restricted PIR protocols
Computational Complexity | 2006-09-28 | Paper |
Enumerations of the Kolmogorov function
Journal of Symbolic Logic | 2006-08-03 | Paper |
Computational depth: Concept and applications
Theoretical Computer Science | 2006-04-28 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
SIAM Journal on Computing | 2005-10-28 | Paper |
Computation in a distributed information market
Theoretical Computer Science | 2005-10-26 | Paper |
| scientific article; zbMATH DE number 2196513 (Why is no real title available?) | 2005-08-22 | Paper |
Prediction and dimension
Journal of Computer and System Sciences | 2005-06-13 | Paper |
Some results on derandomization
Theory of Computing Systems | 2005-04-19 | Paper |
| scientific article; zbMATH DE number 2089375 (Why is no real title available?) | 2004-08-12 | Paper |
scientific article; zbMATH DE number 2079374 (Why is no real title available?)
(available as arXiv preprint) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079416 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2077126 (Why is no real title available?) | 2004-07-01 | Paper |
Separability and one-way functions
Computational Complexity | 2004-05-27 | Paper |
Inverting onto functions.
Information and Computation | 2004-03-14 | Paper |
| scientific article; zbMATH DE number 2038716 (Why is no real title available?) | 2004-02-08 | Paper |
| Kolmogorov complexity | 2004-01-09 | Paper |
| scientific article; zbMATH DE number 1962815 (Why is no real title available?) | 2003-08-11 | Paper |
| scientific article; zbMATH DE number 1962843 (Why is no real title available?) | 2003-08-11 | Paper |
An oracle builder's toolkit
Information and Computation | 2003-07-29 | Paper |
Uniformly hard languages.
Theoretical Computer Science | 2003-05-25 | Paper |
One complexity theorist's view of quantum computing
Theoretical Computer Science | 2003-05-14 | Paper |
Distributionally hard languages
Theory of Computing Systems | 2002-09-11 | Paper |
| scientific article; zbMATH DE number 1775405 (Why is no real title available?) | 2002-08-01 | Paper |
Relativized worlds with an infinite hierarchy
Information Processing Letters | 2002-07-25 | Paper |
Two oracles that force a big crunch
Computational Complexity | 2002-05-05 | Paper |
Resource-bounded Kolmogorov complexity revisited
SIAM Journal on Computing | 2002-04-23 | Paper |
| scientific article; zbMATH DE number 1256638 (Why is no real title available?) | 2002-01-17 | Paper |
| scientific article; zbMATH DE number 1507040 (Why is no real title available?) | 2001-09-04 | Paper |
| scientific article; zbMATH DE number 1497858 (Why is no real title available?) | 2001-03-05 | Paper |
Time-space tradeoffs for satisfiability
Journal of Computer and System Sciences | 2001-02-18 | Paper |
| scientific article; zbMATH DE number 1559596 (Why is no real title available?) | 2001-01-31 | Paper |
| scientific article; zbMATH DE number 1555957 (Why is no real title available?) | 2001-01-24 | Paper |
| scientific article; zbMATH DE number 1860655 (Why is no real title available?) | 2001-01-01 | Paper |
| scientific article; zbMATH DE number 1500532 (Why is no real title available?) | 2000-09-04 | Paper |
On the power of multi-prover interactive protocols
Theoretical Computer Science | 2000-06-15 | Paper |
| scientific article; zbMATH DE number 1335876 (Why is no real title available?) | 2000-05-04 | Paper |
| scientific article; zbMATH DE number 1335896 (Why is no real title available?) | 2000-05-04 | Paper |
| scientific article; zbMATH DE number 1306884 (Why is no real title available?) | 2000-04-26 | Paper |
Separating Complexity Classes Using Autoreducibility
SIAM Journal on Computing | 2000-03-19 | Paper |
Two queries
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Complexity limitations on quantum computation
Journal of Computer and System Sciences | 2000-01-17 | Paper |
| scientific article; zbMATH DE number 1335875 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1335894 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1304314 (Why is no real title available?) | 1999-06-17 | Paper |
On coherence, random-self-reducibility, and self-correction
Computational Complexity | 1999-01-03 | Paper |
