Computer Science

College of Engineering and Physical Sciences

John Hitchcock

Education

• Ph.D. Iowa State University 2003

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

Research Interests
Computational Complexity and Algorithmic Information Theory

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.