J. M. Hitchcock

PROFILE

Homepage
No homepage is listed.
ORCID
No ORCID is listed.
Affiliations
No affiliations are listed.
Aliases
J.m. Hitchcock, John M. Hitchcock
Publication record
52 papers · 780 citations · H-index 16

PAPERS

Polynomial-Time Random Oracles and Separating Complexity Classes
20182 citationsauthor #1
Nonuniform Reductions and NP-Completeness
20182 citationsauthor #1
Nondeterminisic Sublinear Time Has Measure 0 in P
20180 citationsauthor #1
Autoreducibility of NP-Complete Sets under Strong Hypotheses
20171 citationsauthor #1
Autoreducibility of NP-Complete Sets
20161 citationsauthor #1
On the NP-Completeness of the Minimum Circuit Size Problem
201540 citationsauthor #1
Isaac Newton Institute, Cambridge, UK July 2–6, 2012
20130 citationsauthor #5
Length-Increasing Reductions for PSPACE-Completeness
20130 citationsauthor #1
Learning Reductions to Sparse Sets
20132 citationsauthor #3
Base invariance of feasible dimension
20137 citationsauthor #1
Learning Weak Reductions to Sparse Sets
20120 citationsauthor #3
Limitations of Efficient Reducibility to the Kolmogorov Random Strings
20123 citationsauthor #1
Randomness, learnability, and betting games
20120 citationsauthor #1
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
201116 citationsauthor #2
Kolmogorov Complexity in Randomness Extraction
201113 citationsauthor #1
Unions of Disjoint NP-Complete Sets
20111 citationsauthor #2
Lower Bounds for Reducibility to the Kolmogorov Random Strings
20102 citationsauthor #1
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games
20109 citationsauthor #4
Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses
20106 citationsauthor #2
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds
201015 citationsauthor #3
Collapsing and Separating Complete Notions Under Worst-Case and Average-Case Hypotheses
20101 citationsauthor #2
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly
200834 citationsauthor #2
Partial Bi-immunity, Scaled Dimension, and NP-Completeness
200810 citationsauthor #1
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly
20088 citationsauthor #2
The Frequency of Difficult Instances for MaxClique Approximation Algorithms
20070 citationsauthor #1
Dimension, Halfspaces, and the Density of Hard Sets
20079 citationsauthor #2
Strong Reductions and Isomorphism of Complete Sets
20075 citationsauthor #2
Upward separations and weaker hypotheses in resource-bounded measure
20073 citationsauthor #2
Hausdorff dimension and oracle constructions
20068 citationsauthor #1
Comparing reductions to NP-complete sets
200616 citationsauthor #1
Extracting Kolmogorov complexity with applications to dimension zero-one laws
200641 citationsauthor #2
Resource-bounded strong dimension versus resource-bounded category
20055 citationsauthor #1
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
200517 citationsauthor #1
Entropy rates and finite-state dimension
200551 citationsauthor #2
The size of SPP
20046 citationsauthor #1
Dimension, entropy rates, and compression
200422 citationsauthor #1
Effective Strong Dimension in Algorithmic Information and Computational Complexity
200419 citationsauthor #2
Partial bi-immunity and NP-completeness
20040 citationsauthor #1
Hardness Hypotheses, Derandomization, and Circuit Complexity
200420 citationsauthor #1
Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets
20049 citationsauthor #1
Fractal dimension and logarithmic loss unpredictability
200344 citationsauthor #1
The arithmetical complexity of dimension and randomness
200311 citationsauthor #1
Scaled dimension and nonuniform complexity
200332 citationsauthor #1
Effective fractal dimension: foundations and applications
200333 citationsauthor #1
Small spans in scaled dimension
200315 citationsauthor #1
Effective Strong Dimension, Algorithmic Information, and Computational Complexity
2002142 citationsauthor #2
Why Computational Complexity Requires Stricter Martingales
200215 citationsauthor #1
Effective Strong Dimension with Applications to Information and Complexity
20020 citationsauthor #1
MAX3SAT is exponentially hard to approximate if NP has positive dimension
200222 citationsauthor #1
Correspondence Principles for Effective Dimensions
200253 citationsauthor #1
Resource-bounded dimension, nonuniform complexity, and approximation of MAX3SAT
20011 citationsauthor #1
Demonstration of distributed mesh restoration and auto-provisioning in a WDM network using a large optical cross-connect
20009 citationsauthor #9

TIMELINE

2000 9 citations

2001 1 citations

2002 232 citations

2003 135 citations

2004 76 citations

2005 73 citations

2006 65 citations

2007 17 citations

2008 52 citations

2010 33 citations

2011 30 citations

2012 3 citations

2013 9 citations

2015 40 citations

2016 1 citations

2017 1 citations

2018 4 citations

J. M. Hitchcock

PROFILE

PAPERS

TIMELINE

COAUTHOR MAP

CONCEPT FOOTPRINT