| Publication | Date of Publication | Type |
|---|
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 |
Hierarchies for semantic classes
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Beyond NP
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 2079416 (Why is no real title available?)
| 2004-07-28 | Paper |
scientific article; zbMATH DE number 2079374 (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 1962843 (Why is no real title available?)
| 2003-08-11 | Paper |
scientific article; zbMATH DE number 1962815 (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 1335896 (Why is no real title available?)
| 2000-05-04 | Paper |
scientific article; zbMATH DE number 1335876 (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 |
Complexity limitations on quantum computation
Journal of Computer and System Sciences | 2000-01-17 | Paper |
Two queries
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 |
L-Printable Sets
SIAM Journal on Computing | 1998-09-21 | Paper |
On the relative sizes of learnable sets
Theoretical Computer Science | 1998-08-13 | Paper |
scientific article; zbMATH DE number 1136072 (Why is no real title available?)
| 1998-05-12 | Paper |
Gap-definability as a closure property
Information and Computation | 1997-11-18 | Paper |
scientific article; zbMATH DE number 1072530 (Why is no real title available?)
| 1997-10-08 | Paper |
On resource-bounded instance complexity
Theoretical Computer Science | 1997-02-27 | Paper |
Generic separations
Journal of Computer and System Sciences | 1996-07-16 | Paper |
The Isomorphism Conjecture Holds Relative to an Oracle
SIAM Journal on Computing | 1996-04-24 | Paper |
PP is closed under truth-table reductions
Information and Computation | 1996-03-27 | Paper |
scientific article; zbMATH DE number 512854 (Why is no real title available?)
| 1995-10-09 | Paper |
Gap-definable counting classes
Journal of Computer and System Sciences | 1994-12-11 | Paper |
scientific article; zbMATH DE number 697824 (Why is no real title available?)
| 1994-11-30 | Paper |
The power of adaptiveness and additional queries in random-self- reductions
Computational Complexity | 1994-09-01 | Paper |
Algebraic methods for interactive proof systems
Journal of the ACM | 1994-08-21 | Paper |
scientific article; zbMATH DE number 559220 (Why is no real title available?)
| 1994-05-24 | Paper |
\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Computational Complexity | 1994-05-08 | Paper |
Extremes in the degrees of inferability
Annals of Pure and Applied Logic | 1994-05-03 | Paper |
Random-Self-Reducibility of Complete Sets
SIAM Journal on Computing | 1993-12-20 | Paper |
Interactive proof systems and alternating time-space complexity
Theoretical Computer Science | 1993-12-15 | Paper |
Non-deterministic exponential time has two-prover interactive protocols
Computational Complexity | 1993-10-10 | Paper |
Arithmetization: A new method in structural complexity theory
Computational Complexity | 1993-10-10 | Paper |
Addendum to: Non-deterministic exponential time has two-prower interactive protocols
Computational Complexity | 1993-08-15 | Paper |
scientific article; zbMATH DE number 176510 (Why is no real title available?)
| 1993-05-18 | Paper |
On the power of two-local random reductions
Information Processing Letters | 1993-05-16 | Paper |
Are there interactive protocols for co-NP languages?
Information Processing Letters | 1988-01-01 | Paper |
