Some of the content on this website requires JavaScript to be enabled in your web browser to function as intended. While the website is still usable without JavaScript, it should be enabled to enjoy the full interactive experience.

Skip to Main Navigation. Each navigation link will open a list of sub navigation links.

Skip to Main Content

Computer Science|College of Engineering and Applied Science

John Hitchcock

Associate Professor of Computer Science
Adjunct Associate Professor of Mathematics
Room 4084A, Engineering Building
University of Wyoming
College of Engineering and Applied Science
Department of Computer Science
Dept. 3315
1000 E. University Avenue
Laramie, WY 82071
Phone: (307) 766-5341
Research and Course web page
John Hitchcock


  • Ph.D. Iowa State University 2003

Professional Experience

  • Associate Professor, University of Wyoming, 2009-present
  • 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.

Share This Page:

Footer Navigation

University of Wyoming Medallion
1000 E. University Ave. Laramie, WY 82071 // UW Operators (307) 766-1121 // Contact Us // Download Adobe Reader