John M. Hitchcock

Adewale Sekoni

Electron. Colloquium Comput. Complex., 2018

Nondeterminisic Sublinear Time Has Measure 0 in P.

[BibT_eX]

[DOI]

Adewale Sekoni

Electron. Colloquium Comput. Complex., 2018

Nonuniform Reductions and NP-Completeness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Autoreducibility of NP-Complete Sets under Strong Hypotheses.

[BibT_eX]

[DOI]

Comput. Complex., 2018

2016

Autoreducibility of NP-Complete Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

On the NP-Completeness of the Minimum Circuit Size Problem.

[BibT_eX]

[DOI]

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Strong Reductions and Isomorphism of Complete Sets.

[BibT_eX]

[DOI]

Comput., 2014

2013

Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

Base invariance of feasible dimension.

[BibT_eX]

[DOI]

Elvira Mayordomo

Inf. Process. Lett., 2013

Length-Increasing Reductions for PSPACE-Completeness.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Learning Reductions to Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses.

[BibT_eX]

[DOI]

Xiaoyang Gu

Theory Comput. Syst., 2012

Limitations of Efficient Reducibility to the Kolmogorov Random Strings.

[BibT_eX]

[DOI]

Comput., 2012

2011

Dimension, Halfspaces, and the Density of Hard Sets.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., 2011

2010

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Lower Bounds for Reducibility to the Kolmogorov Random Strings.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Kolmogorov Complexity in Randomness Extraction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

2008

Partial Bi-immunity, Scaled Dimension, and NP-Completeness.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.

[BibT_eX]

[DOI]

Harry Buhrman

Electron. Colloquium Comput. Complex., 2008

Hardness Hypotheses, Derandomization, and Circuit Complexity.

[BibT_eX]

[DOI]

Comput. Complex., 2008

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Upward separations and weaker hypotheses in resource-bounded measure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Effective Strong Dimension in Algorithmic Information and Computational Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

2006

Hausdorff dimension and oracle constructions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Why Computational Complexity Requires Stricter Martingales.

[BibT_eX]

[DOI]

Jack H. Lutz

Theory Comput. Syst., 2006

Dimension, entropy rates, and compression.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

Comparing Reductions to NP-Complete Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

2005

Entropy rates and finite-state dimension.

[BibT_eX]

[DOI]

Chris Bourke

Theor. Comput. Sci., 2005

Correspondence Principles for Effective Dimensions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2005

Resource-bounded strong dimension versus resource-bounded category.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

2004

The size of SPP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Small Spans in Scaled Dimension.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Scaled dimension and nonuniform complexity.

[BibT_eX]

[DOI]

Jack H. Lutz

Elvira Mayordomo

J. Comput. Syst. Sci., 2004

The Arithmetical Complexity of Dimension and Randomness

[BibT_eX]

[DOI]

Jack H. Lutz

Sebastiaan Terwijn

Electron. Colloquium Comput. Complex., 2004

Scaled dimension and the Kolmogorov complexity of Turing hard sets

[BibT_eX]

[DOI]

María López-Valdés

Elvira Mayordomo

Electron. Colloquium Comput. Complex., 2004

Partial Bi-Immunity and NP-Completeness

[BibT_eX]

[DOI]

Pramodchandran N. Variyam

Electron. Colloquium Comput. Complex., 2004

Partial Bi-immunity and NP-Completeness.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Fractal dimension and logarithmic loss unpredictability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Gales suffice for constructive dimension.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

2002

MAX3SAT is exponentially hard to approximate if NP has positive dimension.

[BibT_eX]

[DOI]