John Hitchcock
John Hitchcock
Professor of Computer Science
Adjunct Professor of Mathematics
Education
- Ph.D. Iowa State University 2003
Research Interests
- Computational Complexity and Algorithmic Information Theory
Professional Experience
- Professor, University of Wyoming, 2015-Present
- Associate Professor, University of Wyoming, 2009-2015
- Scientific Staff Member, Centrum Wiskunde & Informatica, 2009-2010 (sabbatical appointment)
- Assistant Professor, University of Wyoming, 2003-2009
Selected Publications
- John M. Hitchcock, Limitations of Efficient Reducibility to the Kolmogorov Random
Strings, Computability, 2012.
- Xiaoyang Gu, John M. Hitchcock, and A. Pavan., Collapsing and Separating Completeness
Notions Under Worst-Case and Average-Case Hypotheses, Theory of Computing Systems,
2012.
- John M. Hitchcock, A. Pavan, and N. V. Vinodchandran., Kolmogorov Complexity in Randomness
Extraction, ACM Transactions on Computation Theory, 2011.
- Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, and Akinori Kawachi., Derandomizing
Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.
Computational Complexity, 2011.
- Ryan C. Harkins and John M. Hitchcock., Dimension, Halfspaces, and the Density of
Hard Sets., Theory of Computing Systems, 2011.
- Lance Fortnow, John M. Hitchcock, A. Pavan, N. V. Vinodchandran, and Fengming Wang.,
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws., Information
and Computation, 2011.
- Ryan C. Harkins and John M. Hitchcock., Exact Learning Algorithms, Betting Games,
and Circuit Lower Bounds., International Colloquium on Automata, Languages, and Programming
(ICALP), 2011.
- Christian Glasser, John M. Hitchcock, A. Pavan, and Stephen Travers., Unions of Disjoint
NP-Complete Sets., Computing and Combinatorics Conference (COCOON), 2011.
