John Hitchcock - Publications

John M. Hitchcock's Publications

Research Papers

Random Permutations in Computational Complexity.
John M. Hitchcock, Adewale Sekoni, and Hadi Shafei.
International Symposium on Mathematical Foundations of Computer Science (MFCS), 2025, to appear.
Counting Martingales for Measure and Dimension in Complexity Classes.
John M. Hitchcock, Adewale Sekoni, and Hadi Shafei.
Computational Complexity Conference (CCC), 2025.
Nonuniform Reductions and NP-Completeness.
John M. Hitchcock and Hadi Shafei.
Theory of Computing Systems, 2022.
Polynomial-Time Random Oracles and Separating Complexity Classes.
John M. Hitchcock, Adewale Sekoni, and Hadi Shafei
ACM Transactions on Computation Theory, 2021.
Nondeterministic Sublinear Time Has Measure 0 in P.
John M. Hitchcock and Adewale Sekoni.
Theory of Computing Systems, 2019.
Autoreducibility of NP-Complete Sets under Strong Hypotheses.
John M. Hitchcock and Hadi Shafei.
Computational Complexity, 2018.
On the NP-Completeness of the Minimum Circuit Size Problem.
John M. Hitchcock and A. Pavan.
Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2015.
Strong Reductions and Isomorphism of Complete Sets.
Ryan C. Harkins, John M. Hitchcock, and A. Pavan.
Computability, 2014.
Unions of Disjoint NP-Complete Sets.
Christian Glaßer, John M. Hitchcock, A. Pavan, and Stephen Travers.
ACM Transactions on Computation Theory, 2014.
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.
Length-Increasing Reductions for PSPACE-Completeness.
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.
ACM Transactions on Computation Theory, 2013.
Base Invariance of Feasible Dimension.
John M. Hitchcock and Elvira Mayordomo.
Information Processing Letters, 2013.

Limitations of Efficient Reducibility to the Kolmogorov Random Strings.
John M. Hitchcock.
Computability, 2012.
Collapsing and Separating Completeness Notions Under Worst-Case and Average-Case Hypotheses.
Xiaoyang Gu, John M. Hitchcock, and A. Pavan.
Theory of Computing Systems, 2012.
Kolmogorov Complexity in Randomness Extraction.
John M. Hitchcock, A. Pavan, and N. V. Vinodchandran.
ACM Transactions on Computation Theory, 2011.
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.
Barış Aydınlıoğlu, Dan Gutfreund, John M. Hitchcock, and Akinori Kawachi.
Computational Complexity, 2011.
Dimension, Halfspaces, and the Density of Hard Sets.
Ryan C. Harkins and John M. Hitchcock.
Theory of Computing Systems, 2011.
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.
Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, and Fengming Wang.
Information and Computation, 2011.
NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly.
Harry Buhrman and John M. Hitchcock.
IEEE Conference on Computational Complexity (CCC), 2008.
Hardness Hypotheses, Derandomization, and Circuit Complexity.
John M. Hitchcock and A. Pavan.
Computational Complexity, 2008.
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets.
John M. Hitchcock, María López-Valdés, and Elvira Mayordomo.
Theory of Computing Systems, 2008.
Partial Bi-immunity, Scaled Dimension, and NP-Completeness.
John M. Hitchcock, A. Pavan, and N. V. Vinodchandran.
Theory of Computing Systems, 2008.
Comparing Reductions to NP-Complete Sets.
John M. Hitchcock and A. Pavan.
Information and Computation, 2007.
Online Learning and Resource-Bounded Dimension:
Winnow Yields New Lower Bounds for Hard Sets.
John M. Hitchcock.
SIAM Journal on Computing, 2007.
The Arithmetical Complexity of Dimension and Randomness.
John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn.
ACM Transactions on Computational Logic, 2007.
Upward Separations and Weaker Hypotheses in Resource-Bounded Measure.
Ryan C. Harkins and John M. Hitchcock.
Theoretical Computer Science, 2007.
Effective Strong Dimension in Algorithmic Information and Computational Complexity.
Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo.
SIAM Journal on Computing, 2007.
Dimension, Entropy Rates, and Compression.
John M. Hitchcock and N. V. Vinodchandran.
Journal of Computer and System Sciences, 2006.
Hausdorff Dimension and Oracle Constructions.
John M. Hitchcock.
Theoretical Computer Science, 2006.
Why Computational Complexity Requires Stricter Martingales.
John M. Hitchcock and Jack H. Lutz.
Theory of Computing Systems, 2006.
Entropy Rates and Finite-State Dimension.
Chris Bourke, John M. Hitchcock, and N. V. Vinodchandran.
Theoretical Computer Science, 2005.
Resource-Bounded Strong Dimension versus Resource-Bounded Category.
John M. Hitchcock and A. Pavan.
Information Processing Letters, 2005.
Correspondence Principles for Effective Dimensions.
John M. Hitchcock.
Theory of Computing Systems, 2005.
Small Spans in Scaled Dimension.
John M. Hitchcock.
SIAM Journal on Computing, 2004.
The Size of SPP.
John M. Hitchcock.
Theoretical Computer Science, 2004.
Scaled Dimension and Nonuniform Complexity.
John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo.
Journal of Computer and System Sciences, 2004.
Fractal Dimension and Logarithmic Loss Unpredictability.
John M. Hitchcock.
Theoretical Computer Science, 2003.
Gales Suffice for Constructive Dimension.
John M. Hitchcock.
Information Processing Letters, 2003.
MAX3SAT is Exponentially Hard to Approximate If NP Has Positive Dimension.
John M. Hitchcock.
Theoretical Computer Science, 2002.

Survey Paper

Fractal Geometry in Complexity Classes.
John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo.
SIGACT News Complexity Theory Column, September 2005.

Theses

Effective Fractal Dimension: Foundations and Applications.
John M. Hitchcock.
Ph.D. Dissertation, Iowa State University, 2003.
Resource-Bounded Dimension, Nonuniform Complexity, and Approximation of MAX3SAT.
John M. Hitchcock.
M.S. Thesis, Iowa State University, 2001.