| Publication | Date of Publication | Type |
|---|
Pseudodeterminism: promises and lowerbounds
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Model counting meets \(F_0\) estimation
ACM Transactions on Database Systems | 2023-11-29 | Paper |
Neighborhood Variants of the KKM Lemma, Lebesgue Covering Theorem, and Sperner's Lemma on the Cube
| 2023-06-21 | Paper |
Perfect zero knowledge: new upperbounds and relativized separations
| 2021-12-01 | Paper |
On Pseudodeterministic Approximation Algorithms.
| 2021-08-04 | Paper |
A note on the advice complexity of multipass randomized logspace
| 2018-03-21 | Paper |
On the NP-Completeness of the Minimum Circuit Size Problem.
| 2017-07-13 | Paper |
Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis
| 2017-04-25 | Paper |
New time-space upperbounds for directed reachability in high-genus and \(H\)-minor-free graphs
| 2017-04-25 | Paper |
A thirty year old conjecture about promise problems
Computational Complexity | 2016-11-30 | Paper |
Space-efficient estimation of statistics over sub-sampled streams
Algorithmica | 2016-03-29 | Paper |
Kolmogorov complexity in randomness extraction
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
On probabilistic space-bounded machines with multiple access to random tape
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Unions of disjoint NP-complete sets
ACM Transactions on Computation Theory | 2015-09-07 | Paper |
Strong reductions and isomorphism of complete sets
Computability | 2015-02-24 | Paper |
Length-increasing reductions for PSPACE-completeness
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
A thirty year old conjecture about promise problems
Automata, Languages, and Programming | 2013-08-12 | Paper |
On the power of unambiguity in log-space
Computational Complexity | 2012-12-27 | Paper |
Collapsing and separating completeness notions under average-case and worst-case hypotheses
Theory of Computing Systems | 2012-12-07 | Paper |
Kolmogorov complexity in randomness extraction
| 2012-10-24 | Paper |
Collapsing and separating completeness notions under average-case and worst-case hypotheses
| 2012-01-23 | Paper |
Unions of disjoint NP-complete sets
Lecture Notes in Computer Science | 2011-08-17 | Paper |
The fault tolerance of NP-hard problems
Information and Computation | 2011-07-27 | Paper |
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Information and Computation | 2011-04-28 | Paper |
Robustness of PSPACE-complete sets
Information Processing Letters | 2010-03-24 | Paper |
2-local random reductions to 3-valued functions
Computational Complexity | 2010-03-15 | Paper |
Resource-bounded strong dimension versus resource-bounded category
Information Processing Letters | 2009-12-04 | Paper |
The Fault Tolerance of NP-Hard Problems
Language and Automata Theory and Applications | 2009-04-02 | Paper |
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
Automata, Languages and Programming | 2009-03-12 | Paper |
Comparing Reductions to NP-Complete Sets
Automata, Languages and Programming | 2009-03-12 | Paper |
Splitting NP-Complete Sets
SIAM Journal on Computing | 2008-10-28 | Paper |
Hardness hypotheses, derandomization, and circuit complexity
Computational Complexity | 2008-08-20 | Paper |
Relations between average-case and worst-case complexity
Theory of Computing Systems | 2008-06-06 | Paper |
Strong Reductions and Isomorphism of Complete Sets
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science | 2008-04-24 | Paper |
Some Results on Average-Case Hardness Within the Polynomial Hierarchy
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science | 2008-04-17 | Paper |
Partial bi-immunity, scaled dimension, and NP-completeness
Theory of Computing Systems | 2008-04-03 | Paper |
Redundancy in Complete Sets
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 |
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy
Theoretical Computer Science | 2007-10-18 | Paper |
Autoreducibility, mitoticity, and immunity
Journal of Computer and System Sciences | 2007-05-30 | Paper |
Comparing reductions to NP-complete sets
Information and Computation | 2007-05-14 | Paper |
Properties of NP‐Complete Sets
SIAM Journal on Computing | 2007-05-03 | Paper |
Theory and Applications of Models of Computation
Lecture Notes in Computer Science | 2007-04-30 | Paper |
Mathematical Foundations of Computer Science 2005
Lecture Notes in Computer Science | 2006-10-20 | Paper |
Fundamentals of Computation Theory
Lecture Notes in Computer Science | 2006-10-20 | Paper |
ON HIGHER ARTHUR-MERLIN CLASSES
International Journal of Foundations of Computer Science | 2005-10-19 | Paper |
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2005-08-12 | Paper |
Some results on derandomization
Theory of Computing Systems | 2005-04-19 | Paper |
Bi-immunity separates strong NP-completeness notions
Information and Computation | 2004-11-23 | Paper |
scientific article; zbMATH DE number 2089956 (Why is no real title available?)
| 2004-08-12 | Paper |
scientific article; zbMATH DE number 2086403 (Why is no real title available?)
| 2004-08-11 | Paper |
scientific article; zbMATH DE number 1962815 (Why is no real title available?)
| 2003-08-11 | Paper |
Distributionally hard languages
Theory of Computing Systems | 2002-09-11 | Paper |
Separation of NP-completeness notions
SIAM Journal on Computing | 2002-04-23 | Paper |
Complete distributional problems, hard languages, and resource-bounded measure
Theoretical Computer Science | 2000-08-21 | Paper |
