| 2018 | UCC | Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks. | Liang Liu, Jun (Jim) Xu, Lance Fortnow |
| 2016 | CLOUD | Randomized Algorithms for Dynamic Storage Load-Balancing. | Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu |
| 2016 | SIGMETRICS | Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing. | Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu |
| 2015 | TAMC | Nondeterministic Separations. | Lance Fortnow |
| 2013 | CiE | A Personal View of the P versus NP Problem. | Lance Fortnow |
| 2013 | MFCS | Learning Reductions to Sparse Sets. | Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff |
| 2011 | ICALP | Robust Simulations and Significant Separations. | Lance Fortnow, Rahul Santhanam |
| 2010 | STACS | Inseparability and Strong Hypotheses for Disjoint NP Pairs. | Lance Fortnow, Jack H. Lutz, Elvira Mayordomo |
| 2009 | ICALP | Unconditional Lower Bounds against Advice. | Harry Buhrman, Lance Fortnow, Rahul Santhanam |
| 2009 | TARK | A computational theory of awareness and decision making. | Nikhil R. Devanur, Lance Fortnow |
| 2009 | TARK | Program equilibria and discounted computation time. | Lance Fortnow |
| 2008 | STOC | Infeasibility of instance compression and succinct PCPs for NP. | Lance Fortnow, Rahul Santhanam |
| 2007 | CSR | Inverting Onto Functions and Polynomial Hierarchy. | Harry Buhrman, Lance Fortnow, Michal Kouck, John D. Rogers, Nikolai K. Vereshchagin |
| 2006 | COLT | Efficient Learning Algorithms Yield Circuit Lower Bounds. | Lance Fortnow, Adam R. Klivans |
| 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 | MFCS | Very Sparse Leaf Languages. | Lance Fortnow, Mitsunori Ogihara |
| 2006 | STACS | Linear Advice for Randomized Logarithmic Space. | Lance Fortnow, Adam R. Klivans |
| 2006 | STACS | Kolmogorov Complexity with Error. | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
| 2005 | STOC | Beyond NP: the work and legacy of Larry Stockmeyer. | Lance Fortnow |
| 2005 | STOC | Hierarchies for semantic classes. | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
| 2005 | STACS | Increasing Kolmogorov Complexity. | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
| 2004 | FOCS | Hierarchy Theorems for Probabilistic Polynomial Time. | Lance Fortnow, Rahul Santhanam |
| 2003 | FCT | Using Depth to Capture Average-Case Complexity. | Luis Antunes, Lance Fortnow, N. V. Vinodchandran |
| 2003 | ICALP | Sophistication Revisited. | Luis Antunes, Lance Fortnow |
| 2003 | ISAAC | Infinitely-Often Autoreducible Sets. | Richard Beigel, Lance Fortnow, Frank Stephan |
| 2003 | SODA | Quantum property testing. | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Rhrig |
| 2003 | SODA | Sublinear-time approximation of Euclidean minimum spanning tree. | Artur Czumaj, Funda Ergn, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
| 2003 | STACS | One Bit of Advice. | Harry Buhrman, Richard Chang, Lance Fortnow |
| 2003 | STACS | Some Results on Derandomization. | Harry Buhrman, Lance Fortnow, Aduri Pavan |
| 2002 | COLT | Prediction and Dimension. | Lance Fortnow, Jack H. Lutz |
| 2001 | FOCS | Testing Random Variables for Independence and Identity. | Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White |
| 2001 | RECOMB | An optimal procedure for gap closing in whole genome shotgun sequencing. | Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow |
| 2000 | FOCS | Testing that distributions are close. | Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White |
| 2000 | STACS | Optimal Proof Systems and Sparse Sets. | Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek |
| 1999 | COCOON | Distributionally-Hard Languages. | Lance Fortnow, Aduri Pavan, Alan L. Selman |
| 1999 | STACS | One-sided Versus Two-sided Error in Probabilistic Computation. | Harry Buhrman, Lance Fortnow |
| 1998 | STOC | NP Might Not Be As Easy As Detecting Unique Solutions. | Richard Beigel, Harry Buhrman, Lance Fortnow |
| 1998 | STACS | Nearly Optimal Language Compression Using Extractors. | Lance Fortnow, Sophie Laplante |
| 1998 | TARK | Beating a Finite Automaton in the Big Match. | Lance Fortnow, Peter G. Kimmel |
| 1997 | ICALP | Results on Resource-Bounded Measure. | Harry Buhrman, Stephen A. Fenner, Lance Fortnow |
| 1997 | STOC | Retraction of Probabilistic Computation and Linear Time. | Lance Fortnow, Michael Sipser |
| 1997 | STACS | Resource-Bounded Kolmogorov Complexity Revisited. | Harry Buhrman, Lance Fortnow |
| 1995 | FOCS | Using Autoreducibility to Separate Complexity Classes. | Harry Buhrman, Lance Fortnow, Leen Torenvliet |
| 1995 | ICALP | Measure, Category and Learning Theory. | Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan |
| 1995 | STACS | Beyond P^(NP) - NEXP. | Stephen A. Fenner, Lance Fortnow |
| 1995 | STACS | Resource-Bounded Instance Complexity (Extended Abstract). | Lance Fortnow, Martin Kummer |
| 1994 | ISAAC | Separability and One-Way Functions. | Lance Fortnow, John D. Rogers |
| 1994 | STOC | Optimality and domination in repeated games with bounded players. | Lance Fortnow, Duke Whang |
| 1993 | STACS | Gap-Definability as a Closure Property. | Stephen A. Fenner, Lance Fortnow, Lide Li |
| 1992 | COLT | Degrees of Inferability. | Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman |
| 1992 | FOCS | The Isomorphism Conjecture Holds Relative to an Oracle | Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz |
| 1991 | ASIACRYPT | On the Power of Two-Local Random Reductions. | Lance Fortnow, Mario Szegedy |
| 1991 | STOC | Checking Computations in Polylogarithmic Time | Lszl Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy |
| 1991 | STACS | Interactive Proof Systems and Alternating Time-Space Complexity. | Lance Fortnow, Carsten Lund |
| 1990 | FOCS | A Characterization of \sharp P Arithmetic Straight Line Programs | Lszl Babai, Lance Fortnow |
| 1990 | FOCS | Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols | Lszl Babai, Lance Fortnow, Carsten Lund |
| 1990 | FOCS | Algebraic Methods for Interactive Proof Systems | Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan |
| 1987 | STOC | The Complexity of Perfect Zero-Knowledge (Extended Abstract) | Lance Fortnow |