John Hitchcock - Publications

John Hitchcock's Publications

Survey Paper	Fractal Geometry in Complexity Classes. John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. SIGACT News Complexity Theory Column, September 2005.
Journal Papers	Hardness Hypotheses, Derandomization, and Circuit Complexity. John M. Hitchcock and A. Pavan. Computational Complexity, to appear. Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. John M. Hitchcock, María López-Valdés, and Elvira Mayordomo. Theory of Computing Systems, to appear. Partial Bi-immunity, Scaled Dimension, and NP-Completeness. John M. Hitchcock, A. Pavan, and N. V. Vinodchandran. Theory of Computing Systems, 2008. Comparing Reductions to NP-Complete Sets. John M. Hitchcock and A. Pavan. Information and Computation, 2007. Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. John M. Hitchcock. SIAM Journal on Computing, 2007. The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. ACM Transactions on Computational Logic, 2007. Effective Strong Dimension in Algorithmic Information and Computational Complexity. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. SIAM Journal on Computing, 2007. Dimension, Entropy Rates, and Compression. John M. Hitchcock and N. V. Vinodchandran. Journal of Computer and System Sciences, 2006. Hausdorff Dimension and Oracle Constructions. John M. Hitchcock. Theoretical Computer Science, 2006. Why Computational Complexity Requires Stricter Martingales. John M. Hitchcock and Jack H. Lutz. Theory of Computing Systems, 2006. Entropy Rates and Finite-State Dimension. Chris Bourke, John M. Hitchcock, and N. V. Vinodchandran. Theoretical Computer Science, 2005. Resource-Bounded Strong Dimension versus Resource-Bounded Category. John M. Hitchcock and A. Pavan. Information Processing Letters, 2005. Correspondence Principles for Effective Dimensions. John M. Hitchcock. Theory of Computing Systems, 2005. Small Spans in Scaled Dimension. John M. Hitchcock. SIAM Journal on Computing, 2004. The Size of SPP. John M. Hitchcock. Theoretical Computer Science, 2004. Scaled Dimension and Nonuniform Complexity. John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Journal of Computer and System Sciences, 2004. Fractal Dimension and Logarithmic Loss Unpredictability. John M. Hitchcock. Theoretical Computer Science, 2003. Gales Suffice for Constructive Dimension. John M. Hitchcock. Information Processing Letters, 2003. MAX3SAT is Exponentially Hard to Approximate If NP Has Positive Dimension. John M. Hitchcock. Theoretical Computer Science, 2002.
Conference Papers	NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly. Harry Buhrman and John M. Hitchcock. IEEE Conference on Computational Complexity (CCC), 2008. Strong Reductions and Isomorphism of Complete Sets. Ryan C. Harkins, John M. Hitchcock, and A. Pavan. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2007. Dimension, Halfspaces, and the Density of Hard Sets. Ryan C. Harkins and John M. Hitchcock. Computing and Combinatorics Conference (COCOON), 2007. Comparing Reductions to NP-Complete Sets. John M. Hitchcock and A. Pavan. International Colloquium on Automata, Languages, and Programming (ICALP), 2006. Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, and Fengming Wang. International Colloquium on Automata, Languages, and Programming (ICALP), 2006. Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. John M. Hitchcock. Symposium on Theoretical Aspects of Computer Science (STACS), 2006. Hardness Hypotheses, Derandomization, and Circuit Complexity. John M. Hitchcock and A. Pavan. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2004. Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. John M. Hitchcock, María López-Valdés, and Elvira Mayordomo. International Symposium on Mathematical Foundations of Computer Science (MFCS), 2004. Partial Bi-immunity and NP-Completeness. John M. Hitchcock, A. Pavan, and N. V. Vinodchandran. IEEE Conference on Computational Complexity (CCC), 2004. Dimension, Entropy Rates, and Compression. John M. Hitchcock and N. V. Vinodchandran. IEEE Conference on Computational Complexity (CCC), 2004. Small Spans in Scaled Dimension. John M. Hitchcock. IEEE Conference on Computational Complexity (CCC), 2004. Effective Strong Dimension in Algorithmic Information and Computational Complexity. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. Symposium on Theoretical Aspects of Computer Science (STACS), 2004. The Arithmetical Complexity of Dimension and Randomness. John M. Hitchcock, Jack H. Lutz, and Sebastiaan A. Terwijn. Annual Conference of the European Association for Computer Science Logic (CSL), 2003. Scaled Dimension and Nonuniform Complexity. John M. Hitchcock, Jack H. Lutz, and Elvira Mayordomo. International Colloquium on Automata, Languages, and Programming (ICALP), 2003. Why Computational Complexity Requires Stricter Martingales. John M. Hitchcock and Jack H. Lutz. International Colloquium on Automata, Languages, and Programming (ICALP), 2002. Correspondence Principles for Effective Dimensions. John M. Hitchcock. International Colloquium on Automata, Languages, and Programming (ICALP), 2002.
Theses	Effective Fractal Dimension: Foundations and Applications. John M. Hitchcock. Ph.D. Dissertation, Iowa State University, 2003. Resource-Bounded Dimension, Nonuniform Complexity, and Approximation of MAX3SAT. John M. Hitchcock. M.S. Thesis, Iowa State University, 2001.