Journal Papers

Conference Papers
 Nonuniform Reductions and NPCompleteness.
John M. Hitchcock and Hadi Shafei.
Symposium on Theoretical Aspects of Computer Science
(STACS), 2018.

Autoreducibility of NPComplete
Sets.
John M. Hitchcock and Hadi Shafei.
Symposium on Theoretical Aspects of Computer Science
(STACS), 2016.

On the NPCompleteness of the Minimum
Circuit Size Problem.
John M. Hitchcock and A. Pavan.
Foundations of Software
Technology and Theoretical Computer Science (FSTTCS), 2015.

Learning Reductions to Sparse Sets.
Harry Buhrman, Lance Fortnow, John M. Hitchcock, and Bruno Loff.
International Symposium on Mathematical Foundations of Computer Science (MFCS),
2013.

LengthIncreasing Reductions for PSPACECompleteness.
John M. Hitchcock and A. Pavan.
International Symposium on Mathematical Foundations of Computer Science (MFCS),
2013.

Exact Learning Algorithms, Betting Games, and Circuit Lower
Bounds.
Ryan C. Harkins and John M. Hitchcock.
International Colloquium on Automata, Languages, and Programming
(ICALP), 2011.

Unions of Disjoint NPComplete Sets.
Christian Glaßer, John M. Hitchcock, A. Pavan, and Stephen Travers.
Computing and Combinatorics Conference (COCOON), 2011.

Lower Bounds for Reducibility to the
Kolmogorov Random Strings.
John M. Hitchcock.
Conference on Computability in Europe (CiE), 2010.

Collapsing and Separating Completeness Notions
Under WorstCase and AverageCase Hypotheses.
Xiaoyang Gu, John M. Hitchcock, and A. Pavan.
Symposium on Theoretical Aspects of Computer Science (STACS),
2010.

Kolmogorov Complexity in Randomness
Extraction.
John M. Hitchcock, A. Pavan, and N. V. Vinodchandran.
Foundations of Software
Technology and Theoretical Computer Science (FSTTCS), 2009.

NPHard Sets are Exponentially Dense Unless coNP ⊆ NP/poly.
Harry Buhrman and John M. Hitchcock.
IEEE Conference on Computational Complexity (CCC), 2008.

Strong Reductions and Isomorphism of Complete
Sets.
Ryan C. Harkins, John M. Hitchcock, and A. Pavan.
Foundations of Software
Technology and Theoretical Computer Science (FSTTCS), 2007.

Dimension, Halfspaces, and the Density of
Hard Sets.
Ryan C. Harkins and John M. Hitchcock.
Computing and Combinatorics Conference (COCOON), 2007.

Comparing Reductions to NPComplete Sets.
John M. Hitchcock and A. Pavan.
International Colloquium on Automata, Languages, and
Programming (ICALP), 2006.

Extracting Kolmogorov Complexity with
Applications to Dimension ZeroOne Laws.
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran,
and Fengming Wang.
International Colloquium on Automata, Languages, and
Programming (ICALP), 2006.

Online Learning and ResourceBounded
Dimension:
Winnow Yields New Lower Bounds for Hard Sets.
John M. Hitchcock.
Symposium on Theoretical Aspects of Computer Science (STACS),
2006.

Hardness Hypotheses, Derandomization, and Circuit
Complexity.
John M. Hitchcock and A. Pavan.
Foundations of Software Technology and
Theoretical Computer Science (FSTTCS), 2004.

Scaled Dimension and the Kolmogorov
Complexity of TuringHard Sets.
John M. Hitchcock, María LópezValdés, and
Elvira Mayordomo.
International Symposium on Mathematical Foundations of Computer Science (MFCS),
2004.

Partial Biimmunity and NPCompleteness.
John M. Hitchcock, A. Pavan, and N. V. Vinodchandran.
IEEE Conference on Computational Complexity (CCC), 2004.

Dimension, Entropy Rates, and Compression.
John M. Hitchcock and N. V. Vinodchandran.
IEEE Conference on Computational Complexity (CCC), 2004.

Small Spans in Scaled Dimension.
John M. Hitchcock.
IEEE Conference on Computational Complexity (CCC), 2004.

Effective Strong Dimension in Algorithmic
Information and Computational Complexity.
Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira
Mayordomo.
Symposium on Theoretical Aspects of Computer Science (STACS), 2004.

The Arithmetical Complexity of Dimension and
Randomness.
John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn.
Annual Conference of the European Association for Computer
Science Logic (CSL), 2003.

Scaled Dimension and Nonuniform Complexity.
John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo.
International Colloquium on
Automata, Languages, and Programming (ICALP), 2003.

Why Computational Complexity Requires Stricter
Martingales.
John M. Hitchcock and Jack H. Lutz.
International
Colloquium on Automata, Languages, and Programming (ICALP), 2002.

Correspondence Principles for Effective
Dimensions.
John M. Hitchcock.
International Colloquium on Automata, Languages, and Programming (ICALP), 2002.

Survey Paper

Theses
