John M. Hitchcock

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Counting Martingales for Measure and Dimension in Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2019

Nondeterminisic Sublinear Time Has Measure 0 in P.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2019

2018

Polynomial-Time Random Oracles and Separating Complexity Classes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Autoreducibility of NP-Complete Sets under Strong Hypotheses.

[BibT_eX]

[DOI]

Comput. Complex., 2018

Nonuniform Reductions and NP-Completeness.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

2016

Autoreducibility of NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 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

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

Limitations of Efficient Reducibility to the Kolmogorov Random Strings.

[BibT_eX]

[DOI]

Comput., 2012

2011

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

[BibT_eX]

[DOI]

Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Unions of Disjoint NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Xiaoyang Gu

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 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]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 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

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

Strong Reductions and Isomorphism of Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 2007

Dimension, Halfspaces, and the Density of Hard Sets.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

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

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

Comparing Reductions to NP-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005

Entropy rates and finite-state dimension.

[BibT_eX]

[DOI]

Chris Bourke

Theor. Comput. Sci., 2005

Resource-bounded strong dimension versus resource-bounded category.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2005

2004

Hausdorff Dimension and Oracle Constructions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Partial Bi-Immunity and NP-Completeness

[BibT_eX]

[DOI]

Pramodchandran N. Variyam

Electron. Colloquium Comput. Complex., 2004

Effective Strong Dimension in Algorithmic Information and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the STACS 2004, 2004

Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets.

[BibT_eX]

[DOI]

María López-Valdés

Elvira Mayordomo

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Hardness Hypotheses, Derandomization, and Circuit Complexity.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Dimension, Entropy Rates, and Compression.

[BibT_eX]

[DOI]

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

Partial Bi-immunity and NP-Completeness.

[BibT_eX]

[DOI]

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

Small Spans in Scaled Dimension.

[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

The Size of SPP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Scaled Dimension and Nonuniform Complexity.

[BibT_eX]

[DOI]

Jack H. Lutz

Elvira Mayordomo

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

The Arithmetical Complexity of Dimension and Randomness.

[BibT_eX]

[DOI]

Jack H. Lutz

Sebastiaan Terwijn

Proceedings of the Computer Science Logic, 17th International Workshop, 2003

2002

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

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Why Computational Complexity Requires Stricter Martingales.

[BibT_eX]

[DOI]

Jack H. Lutz

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Correspondence Principles for Effective Dimensions.

[BibT_eX]

[DOI]