John M. Hitchcock

According to our database, John M. Hitchcock authored at least 44 papers between 2002 and 2018.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2018

Polynomial-Time Random Oracles and Separating Complexity Classes.

John M. Hitchcock, Adewale Sekoni, 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

Nonuniform Reductions and NP-Completeness.

John M. Hitchcock, Hadi Shafei

Electron. Colloquium Comput. Complex., 2018

Autoreducibility of NP-Complete Sets under Strong Hypotheses.

John M. Hitchcock, Hadi Shafei

Comput. Complex., 2018

2016

Autoreducibility of NP-Complete Sets.

John M. Hitchcock, Hadi Shafei

Electron. Colloquium Comput. Complex., 2016

2015

On the NP-Completeness of the Minimum Circuit Size Problem.

John M. Hitchcock, Aduri Pavan

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

2014

Unions of Disjoint NP-Complete Sets.

Christian Glaßer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers

ACM Trans. Comput. Theory, 2014

Strong Reductions and Isomorphism of Complete Sets.

Ryan C. Harkins, John M. Hitchcock, Aduri Pavan

Comput., 2014

2013

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

Ryan C. Harkins, John M. Hitchcock

ACM Trans. Comput. Theory, 2013

Base invariance of feasible dimension.

John M. Hitchcock, Elvira Mayordomo

Inf. Process. Lett., 2013

Length-Increasing Reductions for PSPACE-Completeness.

John M. Hitchcock, Aduri Pavan

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Learning Reductions to Sparse Sets.

Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

2012

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

Xiaoyang Gu, John M. Hitchcock, Aduri Pavan

Theory Comput. Syst., 2012

Limitations of Efficient Reducibility to the Kolmogorov Random Strings.

John M. Hitchcock

Comput., 2012

2011

Dimension, Halfspaces, and the Density of Hard Sets.

Ryan C. Harkins, John M. Hitchcock

Theory Comput. Syst., 2011

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

Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi

Comput. Complex., 2011

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

Lower Bounds for Reducibility to the Kolmogorov Random Strings.

John M. Hitchcock

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Kolmogorov Complexity in Randomness Extraction.

John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran

Electron. Colloquium Comput. Complex., 2009

2008

Partial Bi-immunity, Scaled Dimension, and NP-Completeness.

John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran

Theory Comput. Syst., 2008

NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly.

Harry Buhrman, John M. Hitchcock

Electron. Colloquium Comput. Complex., 2008

Hardness Hypotheses, Derandomization, and Circuit Complexity.

John M. Hitchcock, Aduri Pavan

Comput. Complex., 2008

NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.

Harry Buhrman, John M. Hitchcock

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

The arithmetical complexity of dimension and randomness.

John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

ACM Trans. Comput. Log., 2007

Upward separations and weaker hypotheses in resource-bounded measure.

Ryan C. Harkins, John M. Hitchcock

Theor. Comput. Sci., 2007

Effective Strong Dimension in Algorithmic Information and Computational Complexity.

Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo

SIAM J. Comput., 2007

2006

Hausdorff dimension and oracle constructions.

John M. Hitchcock

Theor. Comput. Sci., 2006

Why Computational Complexity Requires Stricter Martingales.

John M. Hitchcock, Jack H. Lutz

Theory Comput. Syst., 2006

Dimension, entropy rates, and compression.

John M. Hitchcock, N. V. Vinodchandran

J. Comput. Syst. Sci., 2006

Comparing Reductions to NP-Complete Sets.

John M. Hitchcock, Aduri Pavan

Electron. Colloquium Comput. Complex., 2006

2005

Entropy rates and finite-state dimension.

Chris Bourke, John M. Hitchcock, N. V. Vinodchandran

Theor. Comput. Sci., 2005

Correspondence Principles for Effective Dimensions.

John M. Hitchcock

Theory Comput. Syst., 2005

Resource-bounded strong dimension versus resource-bounded category.

John M. Hitchcock, Aduri Pavan

Inf. Process. Lett., 2005

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

John M. Hitchcock

Electron. Colloquium Comput. Complex., 2005

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

2004

The size of SPP.

John M. Hitchcock

Theor. Comput. Sci., 2004

Small Spans in Scaled Dimension.

John M. Hitchcock

SIAM J. Comput., 2004

Scaled dimension and nonuniform complexity.

John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo

J. Comput. Syst. Sci., 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

Partial Bi-Immunity and NP-Completeness

John M. Hitchcock, Aduri Pavan, Pramodchandran N. Variyam

Electron. Colloquium Comput. Complex., 2004

Partial Bi-immunity and NP-Completeness.

John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran

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

2003

Fractal dimension and logarithmic loss unpredictability.

John M. Hitchcock

Theor. Comput. Sci., 2003

Gales suffice for constructive dimension.

John M. Hitchcock

Inf. Process. Lett., 2003

2002

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

John M. Hitchcock

Theor. Comput. Sci., 2002