University of Wyoming Electrical Engineering and Computer Science logo over student

John Hitchcock

John Hitchcock

Professor of Computer Science
Adjunct Professor of Mathematics
Room 4084A, Engineering Building
University of Wyoming
College of Engineering and Physical Sciences
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

  • 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.

Find us on Instagram (Link opens a new window)Find us on Facebook (Link opens a new window)Find us on Twitter (Link opens a new window)Find us on LinkedIn (Link opens a new window)Find us on YouTube (Link opens a new window)