MAX3SAT is exponentially hard to approximate if NP has positive dimension. - John M. Hitchcock (Theor. Comput. Sci., 2002)

Gales suffice for constructive dimension. - John M. Hitchcock (Inf. Process. Lett., 2003)

Fractal dimension and logarithmic loss unpredictability. - John M. Hitchcock (Theor. Comput. Sci., 2003)

Partial Bi-immunity and NP-Completeness. - John M. Hitchcock; Aduri Pavan; N. V. Vinodchandran (CCC, 2004)

Partial Bi-Immunity and NP-Completeness - John M. Hitchcock; Aduri Pavan; Pramodchandran N. Variyam (Electron. Colloquium Comput. Complex., 2004)

Scaled dimension and the Kolmogorov complexity of Turing hard sets - John M. Hitchcock; María López-Valdés; Elvira Mayordomo (Electron. Colloquium Comput. Complex., 2004)

The Arithmetical Complexity of Dimension and Randomness - John M. Hitchcock; Jack H. Lutz; Sebastiaan Terwijn (Electron. Colloquium Comput. Complex., 2004)

Scaled dimension and nonuniform complexity. - John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (J. Comput. Syst. Sci., 2004)

Small Spans in Scaled Dimension. - John M. Hitchcock (SIAM J. Comput., 2004)

The size of SPP. - John M. Hitchcock (Theor. Comput. Sci., 2004)

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws - Lance Fortnow; John M. Hitchcock; Aduri Pavan; N. V. Vinodchandran; Fengming Wang (Electron. Colloquium Comput. Complex., 2005)

Resource-bounded strong dimension versus resource-bounded category. - John M. Hitchcock; Aduri Pavan (Inf. Process. Lett., 2005)

Correspondence Principles for Effective Dimensions. - John M. Hitchcock (Theory Comput. Syst., 2005)

Entropy rates and finite-state dimension. - Chris Bourke; John M. Hitchcock; N. V. Vinodchandran (Theor. Comput. Sci., 2005)

Comparing Reductions to NP-Complete Sets. - John M. Hitchcock; Aduri Pavan (Electron. Colloquium Comput. Complex., 2006)

Dimension, entropy rates, and compression. - John M. Hitchcock; N. V. Vinodchandran (J. Comput. Syst. Sci., 2006)

Why Computational Complexity Requires Stricter Martingales. - John M. Hitchcock; Jack H. Lutz (Theory Comput. Syst., 2006)

Hausdorff dimension and oracle constructions. - John M. Hitchcock (Theor. Comput. Sci., 2006)

Effective Strong Dimension in Algorithmic Information and Computational Complexity. - Krishna B. Athreya; John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (SIAM J. Comput., 2007)

Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. - John M. Hitchcock (SIAM J. Comput., 2007)

Upward separations and weaker hypotheses in resource-bounded measure. - Ryan C. Harkins; John M. Hitchcock (Theor. Comput. Sci., 2007)

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. - Harry Buhrman; John M. Hitchcock (CCC, 2008)

Hardness Hypotheses, Derandomization, and Circuit Complexity. - John M. Hitchcock; Aduri Pavan (Comput. Complex., 2008)

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. - Harry Buhrman; John M. Hitchcock (Electron. Colloquium Comput. Complex., 2008)

Partial Bi-immunity, Scaled Dimension, and NP-Completeness. - John M. Hitchcock; Aduri Pavan; N. V. Vinodchandran (Theory Comput. Syst., 2008)

Kolmogorov Complexity in Randomness Extraction. - John M. Hitchcock; Aduri Pavan; N. V. Vinodchandran (Electron. Colloquium Comput. Complex., 2009)

Lower Bounds for Reducibility to the Kolmogorov Random Strings. - John M. Hitchcock (CiE, 2010)

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. - Scott Aaronson; Baris Aydinlioglu; Harry Buhrman; John M. Hitchcock; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. - Baris Aydinlioglu; Dan Gutfreund; John M. Hitchcock; Akinori Kawachi (Comput. Complex., 2011)

Dimension, Halfspaces, and the Density of Hard Sets. - Ryan C. Harkins; John M. Hitchcock (Theory Comput. Syst., 2011)

Limitations of Efficient Reducibility to the Kolmogorov Random Strings. - John M. Hitchcock (Comput., 2012)

Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses. - Xiaoyang Gu; John M. Hitchcock; Aduri Pavan (Theory Comput. Syst., 2012)

Learning Reductions to Sparse Sets. - Harry Buhrman; Lance Fortnow; John M. Hitchcock; Bruno Loff (MFCS, 2013)

Length-Increasing Reductions for PSPACE-Completeness. - John M. Hitchcock; Aduri Pavan (MFCS, 2013)

Base invariance of feasible dimension. - John M. Hitchcock; Elvira Mayordomo (Inf. Process. Lett., 2013)

Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. - Ryan C. Harkins; John M. Hitchcock (ACM Trans. Comput. Theory, 2013)

Strong Reductions and Isomorphism of Complete Sets. - Ryan C. Harkins; John M. Hitchcock; Aduri Pavan (Comput., 2014)

Unions of Disjoint NP-Complete Sets. - Christian Glaßer; John M. Hitchcock; Aduri Pavan; Stephen D. Travers (ACM Trans. Comput. Theory, 2014)

On the NP-Completeness of the Minimum Circuit Size Problem. - John M. Hitchcock; Aduri Pavan (FSTTCS, 2015)

Autoreducibility of NP-Complete Sets. - John M. Hitchcock; Hadi Shafei (Electron. Colloquium Comput. Complex., 2016)

Autoreducibility of NP-Complete Sets under Strong Hypotheses. - John M. Hitchcock; Hadi Shafei (Comput. Complex., 2018)

Nonuniform Reductions and NP-Completeness. - John M. Hitchcock; Hadi Shafei (Electron. Colloquium Comput. Complex., 2018)

Nondeterminisic Sublinear Time Has Measure 0 in P. - John M. Hitchcock; Adewale Sekoni (Electron. Colloquium Comput. Complex., 2018)

Polynomial-Time Random Oracles and Separating Complexity Classes. - John M. Hitchcock; Adewale Sekoni; Hadi Shafei (Electron. Colloquium Comput. Complex., 2018)

Random Permutations in Computational Complexity. - John M. Hitchcock; Adewale Sekoni; Hadi Shafei (MFCS, 2025)

Counting Martingales for Measure and Dimension in Complexity Classes. - John M. Hitchcock; Adewale Sekoni; Hadi Shafei (Electron. Colloquium Comput. Complex., 2025)