Follow
John Hitchcock
Title
Cited by
Cited by
Year
Effective strong dimension in algorithmic information and computational complexity
KB Athreya, JM Hitchcock, JH Lutz, E Mayordomo
STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science …, 2004
1712004
Correspondence principles for effective dimensions
JM Hitchcock
Theory of Computing Systems 38 (5), 559-571, 2005
642005
Fractal dimension and logarithmic loss unpredictability
JM Hitchcock
Theoretical Computer Science 304 (1-3), 431-441, 2003
542003
Extracting Kolmogorov complexity with applications to dimension zero-one laws
L Fortnow, JM Hitchcock, A Pavan, NV Vinodchandran, F Wang
Information and Computation 209 (4), 627-636, 2011
52*2011
Network auto-provisioning and distributed restoration
N Agrawal, JM Hitchcock, NA Jackman, SK Korotky, ES Tentarelli, ...
US Patent 6,763,190, 2004
512004
Entropy rates and finite-state dimension
C Bourke, JM Hitchcock, NV Vinodchandran
Theoretical Computer Science 349 (3), 392-406, 2005
502005
On the NP-completeness of the minimum circuit size problem
JM Hitchcock, A Pavan
35th IARCS Annual Conference on Foundations of Software Technology and …, 2015
462015
The fractal geometry of complexity classes
JM Hitchcock, JH Lutz, E Mayordomo
SIGACT News 36 (3), 24-38, 2005
402005
Effective fractal dimension: foundations and applications
JM Hitchcock
Iowa State University, 2003
402003
NP-hard sets are exponentially dense unless coNP C NP/poly
H Buhrman, JM Hitchcock
2008 23rd Annual IEEE Conference on Computational Complexity, 1-7, 2008
382008
Scaled dimension and nonuniform complexity
JM Hitchcock, JH Lutz, E Mayordomo
Journal of Computer and System Sciences 69 (2), 97-122, 2004
312004
Gales suffice for constructive dimension
JM Hitchcock
Information Processing Letters 86 (1), 9-12, 2003
312003
Hardness hypotheses, derandomization, and circuit complexity
JM Hitchcock, A Pavan
computational complexity 17 (1), 119-146, 2008
30*2008
MAX3SAT is exponentially hard to approximate if NP has positive dimension
JM Hitchcock
Theoretical Computer Science 289 (1), 861-869, 2002
292002
Dimension, entropy rates, and compression
JM Hitchcock, NV Vinodchandran
Journal of Computer and System Sciences 72 (4), 760-782, 2006
262006
Comparing reductions to NP-complete sets
JM Hitchcock, A Pavan
Information and Computation 205 (5), 694-706, 2007
252007
Small spans in scaled dimension
JM Hitchcock
SIAM Journal on Computing 34 (1), 170-194, 2004
242004
Kolmogorov complexity in randomness extraction
JM Hitchcock, A Pavan, NV Vinodchandran
ACM Transactions on Computation Theory (TOCT) 3 (1), 1-12, 2011
222011
Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets
JM Hitchcock
SIAM Journal on Computing 36 (6), 1696-1708, 2007
212007
Why computational complexity requires stricter martingales
JM Hitchcock, JH Lutz
Theory of computing systems 39 (2), 277-296, 2006
21*2006
The system can't perform the operation now. Try again later.
Articles 1–20