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 | 171 | 2004 |
Correspondence principles for effective dimensions JM Hitchcock Theory of Computing Systems 38 (5), 559-571, 2005 | 65 | 2005 |
Fractal dimension and logarithmic loss unpredictability JM Hitchcock Theoretical Computer Science 304 (1-3), 431-441, 2003 | 54 | 2003 |
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 | 53* | 2011 |
Entropy rates and finite-state dimension C Bourke, JM Hitchcock, NV Vinodchandran Theoretical Computer Science 349 (3), 392-406, 2005 | 51 | 2005 |
Network auto-provisioning and distributed restoration N Agrawal, JM Hitchcock, NA Jackman, SK Korotky, ES Tentarelli, ... US Patent 6,763,190, 2004 | 51 | 2004 |
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 | 46 | 2015 |
The fractal geometry of complexity classes JM Hitchcock, JH Lutz, E Mayordomo SIGACT News 36 (3), 24-38, 2005 | 41 | 2005 |
Effective fractal dimension: foundations and applications JM Hitchcock Iowa State University, 2003 | 40 | 2003 |
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 | 39 | 2008 |
Gales suffice for constructive dimension JM Hitchcock Information Processing Letters 86 (1), 9-12, 2003 | 32 | 2003 |
Scaled dimension and nonuniform complexity JM Hitchcock, JH Lutz, E Mayordomo Journal of Computer and System Sciences 69 (2), 97-122, 2004 | 31 | 2004 |
Hardness hypotheses, derandomization, and circuit complexity JM Hitchcock, A Pavan computational complexity 17 (1), 119-146, 2008 | 29* | 2008 |
MAX3SAT is exponentially hard to approximate if NP has positive dimension JM Hitchcock Theoretical Computer Science 289 (1), 861-869, 2002 | 29 | 2002 |
Dimension, entropy rates, and compression JM Hitchcock, NV Vinodchandran Journal of Computer and System Sciences 72 (4), 760-782, 2006 | 26 | 2006 |
Comparing reductions to NP-complete sets JM Hitchcock, A Pavan Information and Computation 205 (5), 694-706, 2007 | 25 | 2007 |
Small spans in scaled dimension JM Hitchcock SIAM Journal on Computing 34 (1), 170-194, 2004 | 24 | 2004 |
Kolmogorov complexity in randomness extraction JM Hitchcock, A Pavan, NV Vinodchandran ACM Transactions on Computation Theory (TOCT) 3 (1), 1-12, 2011 | 22 | 2011 |
Why computational complexity requires stricter martingales JM Hitchcock, JH Lutz Theory of computing systems 39 (2), 277-296, 2006 | 22* | 2006 |
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 | 21 | 2007 |