| 2026 | CiE | Counting Random Oracles for the Polynomial-Time Hierarchy and Quantum Complexity Classes. | John M. Hitchcock, Adewale Sekoni, Hadi Shafei |
| 2025 | MFCS | Random Permutations in Computational Complexity. | John M. Hitchcock, Adewale Sekoni, Hadi Shafei |
| 2018 | STACS | Nonuniform Reductions and NP-Completeness. | John M. Hitchcock, Hadi Shafei |
| 2016 | STACS | Autoreducibility of NP-Complete Sets. | John M. Hitchcock, Hadi Shafei |
| 2013 | MFCS | Learning Reductions to Sparse Sets. | Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff |
| 2013 | MFCS | Length-Increasing Reductions for PSPACE-Completeness. | John M. Hitchcock, Aduri Pavan |
| 2011 | COCOON | Unions of Disjoint NP-Complete Sets. | Christian Glaer, John M. Hitchcock, Aduri Pavan, Stephen D. Travers |
| 2011 | ICALP | Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds. | Ryan C. Harkins, John M. Hitchcock |
| 2010 | CiE | Lower Bounds for Reducibility to the Kolmogorov Random Strings. | John M. Hitchcock |
| 2010 | STACS | Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses. | Xiaoyang Gu, John M. Hitchcock, Aduri Pavan |
| 2007 | COCOON | Dimension, Halfspaces, and the Density of Hard Sets. | Ryan C. Harkins, John M. Hitchcock |
| 2006 | ICALP | Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. | Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang |
| 2006 | ICALP | Comparing Reductions to NP-Complete Sets. | John M. Hitchcock, Aduri Pavan |
| 2006 | STACS | Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. | John M. Hitchcock |
| 2004 | MFCS | Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. | John M. Hitchcock, Mara Lpez-Valds, Elvira Mayordomo |
| 2004 | STACS | Effective Strong Dimension in Algorithmic Information and Computational Complexity. | Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
| 2003 | CSL | The Arithmetical Complexity of Dimension and Randomness. | John M. Hitchcock, Jack H. Lutz, Sebastiaan Terwijn |
| 2003 | ICALP | Scaled Dimension and Nonuniform Complexity. | John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
| 2002 | ICALP | Correspondence Principles for Effective Dimensions. | John M. Hitchcock |
| 2002 | ICALP | Why Computational Complexity Requires Stricter Martingales. | John M. Hitchcock, Jack H. Lutz |