John Hitchcock - Publications

John Hitchcock's Publications

Journal Papers

Polynomial-Time Random Oracles and Separating Complexity Classes.
John M. Hitchcock, Hadi Shafei, and Adewale Sekoni.
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.
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.
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.
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.

Conference Papers

Nonuniform Reductions and NP-Completeness.
John M. Hitchcock and Hadi Shafei.
Symposium on Theoretical Aspects of Computer Science (STACS), 2018.
Autoreducibility of NP-Complete Sets.
John M. Hitchcock and Hadi Shafei.
Symposium on Theoretical Aspects of Computer Science (STACS), 2016.
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.
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.
International Colloquium on Automata, Languages, and Programming (ICALP), 2011.
Unions of Disjoint NP-Complete 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 Worst-Case and Average-Case 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.
NP-Hard 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 NP-Complete Sets.
John M. Hitchcock and A. Pavan.
International Colloquium on Automata, Languages, and Programming (ICALP), 2006.
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One 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 Resource-Bounded 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 Turing-Hard Sets.
John M. Hitchcock, María López-Valdés, and Elvira Mayordomo.
International Symposium on Mathematical Foundations of Computer Science (MFCS), 2004.
Partial Bi-immunity and NP-Completeness.
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

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.