| Publication | Date of Publication | Type |
|---|
Nonuniform reductions and NP-completeness
Theory of Computing Systems | 2022-07-26 | Paper |
Polynomial-time random oracles and separating complexity classes
ACM Transactions on Computation Theory | 2022-03-14 | Paper |
Nonuniform reductions and NP-completeness
| 2020-08-05 | Paper |
Nondeterminisic sublinear time has measure 0 in P
Theory of Computing Systems | 2019-06-27 | Paper |
Autoreducibility of NP-complete sets under strong hypotheses
Computational Complexity | 2018-04-18 | Paper |
Autoreducibility of NP-complete sets
| 2018-01-24 | Paper |
On the NP-Completeness of the Minimum Circuit Size Problem.
| 2017-07-13 | Paper |
The arithmetical complexity of dimension and randomness
ACM Transactions on Computational Logic | 2017-07-12 | Paper |
Kolmogorov complexity in randomness extraction
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Exact learning algorithms, betting games, and circuit lower bounds
ACM Transactions on Computation Theory | 2015-09-24 | 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 |
Base invariance of feasible dimension
Information Processing Letters | 2014-04-11 | Paper |
Learning Reductions to Sparse Sets
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Length-increasing reductions for PSPACE-completeness
Mathematical Foundations of Computer Science 2013 | 2013-09-20 | Paper |
Limitations of efficient reducibility to the Kolmogorov random strings
Computability | 2013-01-30 | 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 |
Dimension, halfspaces, and the density of hard sets
Theory of Computing Systems | 2011-11-30 | Paper |
Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
Computational Complexity | 2011-11-08 | Paper |
Unions of disjoint NP-complete sets
Lecture Notes in Computer Science | 2011-08-17 | Paper |
Exact learning algorithms, betting games, and circuit lower bounds
Automata, Languages and Programming | 2011-07-06 | Paper |
Extracting Kolmogorov complexity with applications to dimension zero-one laws
Information and Computation | 2011-04-28 | Paper |
Lower bounds for reducibility to the Kolmogorov random strings
Programs, Proofs, Processes | 2010-07-29 | Paper |
Resource-bounded strong dimension versus resource-bounded category
Information Processing Letters | 2009-12-04 | Paper |
Scaled dimension and the Kolmogorov complexity of Turing-hard sets
Theory of Computing Systems | 2009-05-08 | Paper |
Gales suffice for constructive dimension
Information Processing Letters | 2009-03-23 | 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 |
Dimension, Halfspaces, and the Density of Hard Sets
Lecture Notes in Computer Science | 2009-03-06 | Paper |
Hardness hypotheses, derandomization, and circuit complexity
Computational Complexity | 2008-08-20 | Paper |
Effective Strong Dimension in Algorithmic Information and Computational Complexity
SIAM Journal on Computing | 2008-06-19 | Paper |
Strong Reductions and Isomorphism of Complete Sets
FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science | 2008-04-24 | Paper |
Partial bi-immunity, scaled dimension, and NP-completeness
Theory of Computing Systems | 2008-04-03 | Paper |
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
STACS 2006 | 2008-03-19 | Paper |
Upward separations and weaker hypotheses in resource-bounded measure
Theoretical Computer Science | 2008-01-07 | Paper |
Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
SIAM Journal on Computing | 2008-01-03 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Computer Science Logic
Lecture Notes in Computer Science | 2007-06-21 | Paper |
Comparing reductions to NP-complete sets
Information and Computation | 2007-05-14 | Paper |
Why computational complexity requires stricter martingales
Theory of Computing Systems | 2006-10-25 | Paper |
Dimension, entropy rates, and compression
Journal of Computer and System Sciences | 2006-06-30 | Paper |
Hausdorff dimension and oracle constructions
Theoretical Computer Science | 2006-04-28 | Paper |
Entropy rates and finite-state dimension
Theoretical Computer Science | 2006-03-20 | Paper |
Correspondence principles for effective dimensions
Theory of Computing Systems | 2006-02-08 | Paper |
Mathematical Foundations of Computer Science 2004
Lecture Notes in Computer Science | 2005-08-22 | Paper |
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2005-08-12 | Paper |
Small Spans in Scaled Dimension
SIAM Journal on Computing | 2005-02-21 | Paper |
Scaled dimension and nonuniform complexity
Journal of Computer and System Sciences | 2004-10-01 | Paper |
scientific article; zbMATH DE number 2086652 (Why is no real title available?)
| 2004-08-11 | Paper |
scientific article; zbMATH DE number 2086651 (Why is no real title available?)
| 2004-08-11 | Paper |
The size of SPP
Theoretical Computer Science | 2004-08-10 | Paper |
scientific article; zbMATH DE number 2038717 (Why is no real title available?)
| 2004-02-08 | Paper |
Fractal dimension and logarithmic loss unpredictability.
Theoretical Computer Science | 2003-08-17 | Paper |
MAX3SAT is exponentially hard to approximate if NP has positive dimension.
Theoretical Computer Science | 2003-01-21 | Paper |
