Lance Fortnow

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. J. ACM 60(1): 4 (2013)

Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Computational Complexity 21(3): 479-497 (2012)

Lance Fortnow: The Enduring Legacy of the Turing Machine. Comput. J. 55(7): 830-831 (2012)

Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51(2): 229-247 (2012)

Lance Fortnow, Rahul Sami: Multi-outcome and Multidimensional Market Scoring Rules. CoRR abs/1202.1712 (2012)

Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov complexity with applications to dimension zero-one laws. Inf. Comput. 209(4): 627-636 (2011)

Lance Fortnow, Joshua A. Grochow: Complexity classes of equivalence problems revisited. Inf. Comput. 209(4): 748-763 (2011)

Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)

Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580

Michele Budinich, Lance Fortnow: Repeated matching pennies with limited randomness. ACM Conference on Electronic Commerce 2011: 111-118

Lance Fortnow, Salil P. Vadhan (Eds.): Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011. ACM 2011, isbn 978-1-4503-0691-1

Michele Budinich, Lance Fortnow: Repeated Matching Pennies with Limited Randomness. CoRR abs/1102.1096 (2011)

Yiling Chen, Stanko Dimitrov, Rahul Sami, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen: Gaming Prediction Markets: Equilibrium Strategies with a Market Maker. Algorithmica 58(4): 930-969 (2010)

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? Theory Comput. Syst. 46(1): 143-156 (2010)

Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. IEEE Conference on Computational Complexity 2010: 58-63

Lance Fortnow, Rahul Santhanam: Bounding Rationality by Discounting Time. ICS 2010: 143-155

Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS 2010: 395-404

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010)

Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010)

Lance Fortnow: Viewpoint - Time for computer science to grow up. Commun. ACM 52(8): 33-35 (2009)

Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009)

Lance Fortnow, Adam R. Klivans: Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75(1): 27-36 (2009)

Luis Filipe Coelho Antunes, Lance Fortnow: Sophistication Revisited. Theory Comput. Syst. 45(1): 150-161 (2009)

Lance Fortnow: A Simple Proof of Toda's Theorem. Theory of Computing 5(1): 135-140 (2009)

Lance Fortnow: Editor's Foreword. TOCT 1(1) (2009)

Lance Fortnow, Rahul Santhanam, Ryan Williams: Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26

Luis Filipe Coelho Antunes, Lance Fortnow: Worst-Case Running Times for Average-Case Algorithms. IEEE Conference on Computational Complexity 2009: 298-303

Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209

Nikhil R. Devanur, Lance Fortnow: A computational theory of awareness and decision making. TARK 2009: 99-107

Lance Fortnow: Program equilibria and discounted computation time. TARK 2009: 128-133

John Chuang, Lance Fortnow, Pearl Pu (Eds.): Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009. ACM 2009, isbn 978-1-60558-458-4

Lance Fortnow, Joshua A. Grochow: Complexity Classes of Equivalence Problems Revisited. CoRR abs/0907.4775 (2009)

Lance Fortnow, Rahul Santhanam: Bounding Rationality by Discounting Time. CoRR abs/0911.3162 (2009)

Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. CoRR abs/0912.3162 (2009)

Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009)

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 (2008)

Lance Fortnow, Aduri Pavan, Samik Sengupta: Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci. 74(3): 358-363 (2008)

Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)

Lance Fortnow, Rakesh V. Vohra: The complexity of forecast testing. SIGecom Exchanges 7(3) (2008)

Lance Fortnow, Rakesh Vohra: The complexity of forecast testing: abstract. ACM Conference on Electronic Commerce 2008: 139

Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of combinatorial market makers. ACM Conference on Electronic Commerce 2008: 190-199

Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142

Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007. Dagstuhl Seminar Proceedings 07411, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008

Lance Fortnow, John Riedl, Tuomas Sandholm (Eds.): Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008. ACM 2008, isbn 978-1-60558-169-9

Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of Combinatorial Market Makers. CoRR abs/0802.1362 (2008)

Nikhil R. Devanur, Lance Fortnow: A Computational Theory of Awareness and Decision Making. Electronic Colloquium on Computational Complexity (ECCC) 15(046) (2008)

Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Combinatorial betting. SIGecom Exchanges 7(1): 61-64 (2007)

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. IEEE Conference on Computational Complexity 2007: 46-51

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103

Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007

Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007

Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Betting on permutations. ACM Conference on Electronic Commerce 2007: 326-335

Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen: Bluffing and Strategic Reticence in Prediction Markets. WINE 2007: 70-81

Lance Fortnow, Rahul Santhanam: Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004) (2007)

Lance Fortnow, Rahul Santhanam: Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096) (2007)

Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet: Enumerations of the Kolmogorov function. J. Symb. Log. 71(2): 501-528 (2006)

Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)

Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran: Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006)

Eldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. Theory of Computing 2(1): 173-183 (2006)

Lance Fortnow, Adam R. Klivans: Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363

Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. ICALP (1) 2006: 335-345

Lance Fortnow, Mitsunori Ogihara: Very Sparse Leaf Languages. MFCS 2006: 375-386

Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148

Lance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space. STACS 2006: 469-476

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting onto functions might not be hard. Electronic Colloquium on Computational Complexity (ECCC) 13(024) (2006)

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Electronic Colloquium on Computational Complexity (ECCC) 13(125) (2006)

Lance Fortnow, Rakesh Vohra: The Complexity of Forecast Testing. Electronic Colloquium on Computational Complexity (ECCC) 13(149) (2006)

Lance Fortnow, Rahul Santhanam: Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157) (2006)

Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman: Betting Boolean-style: a framework for trading in securities based on logical formulas. Decision Support Systems 39(1): 87-104 (2005)

Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)

Lance Fortnow, Jack H. Lutz: Prediction and dimension. J. Comput. Syst. Sci. 70(4): 570-589 (2005)

Harry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005)

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time. SIAM J. Comput. 35(1): 91-109 (2005)

Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami: Computation in a distributed information market. Theor. Comput. Sci. 343(1-2): 114-132 (2005)

Eldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. IEEE Conference on Computational Complexity 2005: 135-140

Lance Fortnow, Adam R. Klivans: NP with Small Advice. IEEE Conference on Computational Complexity 2005: 228-234

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. IEEE Conference on Computational Complexity 2005: 323-332

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421

Lance Fortnow: Beyond NP: the work and legacy of Larry Stockmeyer. STOC 2005: 120-127

Lance Fortnow, Rahul Santhanam, Luca Trevisan: Hierarchies for semantic classes. STOC 2005: 348-355

Harry Buhrman, Lance Fortnow, Thomas Thierauf (Eds.): Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005

Lance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space. Electronic Colloquium on Computational Complexity (ECCC)(042) (2005)

Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang: Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. Electronic Colloquium on Computational Complexity (ECCC)(105) (2005)

Lance Fortnow, Luis Antunes: Time-Bounded Universal Distributions. Electronic Colloquium on Computational Complexity (ECCC)(144) (2005)

Lance Fortnow: Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. SIGACT News 35(2): 16-18 (2004)

Harry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004

Lance Fortnow, Rahul Santhanam: Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the complexity of succinct zero-sum games. Electronic Colloquium on Computational Complexity (ECCC)(001) (2004)

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrei A. Muchnik, Frank Stephan, Leen Torenvliet: Enumerations of the Kolmogorov Function. Electronic Colloquium on Computational Complexity (ECCC)(015) (2004)

Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. Electronic Colloquium on Computational Complexity (ECCC)(080) (2004)

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC)(081) (2004)

Lance Fortnow, Rahul Santhanam, Luca Trevisan: Promise Hierarchies. Electronic Colloquium on Computational Complexity (ECCC)(098) (2004)

Lance Fortnow, Adam R. Klivans: NP with Small Advice. Electronic Colloquium on Computational Complexity (ECCC)(103) (2004)

Eldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. Electronic Colloquium on Computational Complexity (ECCC)(105) (2004)

Lance Fortnow, Steven Homer: A Short History of Computational Complexity. Bulletin of the EATCS 80: 95-133 (2003)

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li: An oracle builder's toolkit. Inf. Comput. 182(2): 95-136 (2003)

Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers: Inverting onto functions. Inf. Comput. 186(1): 90-103 (2003)

Rodney G. Downey, Lance Fortnow: Uniformly hard languages. Theor. Comput. Sci. 2(298): 303-315 (2003)

Lance Fortnow: One complexity theorist's view of quantum computing. Theor. Comput. Sci. 292(3): 597-610 (2003)

Richard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336

Lance Fortnow, Aduri Pavan, Samik Sengupta: Proving SAT does not have Small Circuits with an Application to the Two. IEEE Conference on Computational Complexity 2003: 347-

Luis Antunes, Lance Fortnow, N. V. Vinodchandran: Using Depth to Capture Average-Case Complexity. FCT 2003: 303-310

Luis Antunes, Lance Fortnow: Sophistication Revisited. ICALP 2003: 267-277

Richard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107

Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman: Betting boolean-style: a framework for trading in securities based on logical formulas. ACM Conference on Electronic Commerce 2003: 144-155

Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami: Computation in a distributed information market. ACM Conference on Electronic Commerce 2003: 156-165

Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler: Sublinear-time approximation of Euclidean minimum spanning tree. SODA 2003: 813-822

Harry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. STACS 2003: 212-222

Harry Buhrman, Richard Chang, Lance Fortnow: One Bit of Advice. STACS 2003: 547-558

Richard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols. Electronic Colloquium on Computational Complexity (ECCC)(087) (2003)

Lance Fortnow, John D. Rogers: Separability and one-way functions. Computational Complexity 11(3-4): 137-157 (2002)

Lance Fortnow: The History of Complexity. IEEE Conference on Computational Complexity 2002: 61

Lance Fortnow, Jack H. Lutz: Prediction and Dimension. COLT 2002: 380-395

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet: Two oracles that force a big crunch. Computational Complexity 10(2): 93-116 (2001)

Lance Fortnow: Guest Editor's Foreword. J. Comput. Syst. Sci. 62(2): 215 (2001)

Lance Fortnow, Aduri Pavan, Alan L. Selman: Distributionally Hard Languages. Theory Comput. Syst. 34(3): 245-261 (2001)

Harry Buhrman, Lance Fortnow, Sophie Laplante: Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. 31(3): 887-905 (2001)

Lance Fortnow: Diagonalization. Current Trends in Theoretical Computer Science 2001: 102-114

Lance Fortnow: Comparing Notions of Full Derandomization. IEEE Conference on Computational Complexity 2001: 28-34

Luis Antunes, Lance Fortnow, Dieter van Melkebeek: Computational Depth. IEEE Conference on Computational Complexity 2001: 266-273

Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White: Testing Random Variables for Independence and Identity. FOCS 2001: 442-451

Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow: An optimal procedure for gap closing in whole genome shotgun sequencing. RECOMB 2001: 22-30

Lance Fortnow: Diagonalization. Bulletin of the EATCS 71: 102-113 (2000)

Lance Fortnow: Time-Space Tradeoffs for Satisfiability. J. Comput. Syst. Sci. 60(2): 337-353 (2000)

Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet: Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000)

Lance Fortnow: One complexity theorist's view of quantum computing. Electr. Notes Theor. Comput. Sci. 31: 58-72 (2000)

Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 2000: 2-13

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing that distributions are close. FOCS 2000: 259-269

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek: Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418

Lance Fortnow: One Complexity Theorist's View of Quantum Computing. CoRR quant-ph/0003035 (2000)

Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(28) (2000)

Lance Fortnow: Relativized Worlds with an Infinite Hierarchy. Inf. Process. Lett. 69(6): 309-313 (1999)

Harry Buhrman, Lance Fortnow: Two Queries. J. Comput. Syst. Sci. 59(2): 182-194 (1999)

Lance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. J. Comput. Syst. Sci. 59(2): 240-252 (1999)

Lance Fortnow: Book review: of Bounded Queries in Recursion Theory by William A. Gasarch and Georgia A. Martin (Birkhauser. Boston, Basel, Berlin, 1999). SIGACT News 30(3): 13-15 (1999)

Lance Fortnow, Aduri Pavan, Alan L. Selman: Distributionally-Hard Languages. COCOON 1999: 184-193

Harry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109

Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik: On Coherence, Random-Self-Reducibility, and Self-Correction. Computational Complexity 7(2): 174-191 (1998)

Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney: L-Printable Sets. SIAM J. Comput. 28(1): 137-151 (1998)

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan: On the Relative Sizes of Learnable Sets. Theor. Comput. Sci. 197(1-2): 139-156 (1998)

Harry Buhrman, Lance Fortnow, Thomas Thierauf: Nonrelativizing Separations. IEEE Conference on Computational Complexity 1998: 8-12

Harry Buhrman, Lance Fortnow: Two Queries. IEEE Conference on Computational Complexity 1998: 13-

Lance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. IEEE Conference on Computational Complexity 1998: 202-209

Rodney G. Downey, Lance Fortnow: Uniformly Hard Languages. IEEE Conference on Computational Complexity 1998: 228-

Lance Fortnow, Sophie Laplante: Nearly Optimal Language Compression Using Extractors. STACS 1998: 84-93

Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208

Lance Fortnow, Peter G. Kimmel: Beating a Finite Automaton in the Big Match. TARK 1998: 225-234

Lance Fortnow, John D. Rogers: Complexity limitations on quantum computation. CoRR cs.CC/9811023 (1998)

Harry Buhrman, Lance Fortnow, Leen Torenvliet: Six Hypotheses in Search of a Theorem. IEEE Conference on Computational Complexity 1997: 2-12

Lance Fortnow: Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. IEEE Conference on Computational Complexity 1997: 52-60

Harry Buhrman, Stephen A. Fenner, Lance Fortnow: Results on Resource-Bounded Measure. ICALP 1997: 188-194

Harry Buhrman, Lance Fortnow: Resource-Bounded Kolmogorov Complexity Revisited. STACS 1997: 105-116

Lance Fortnow, Michael Sipser: Retraction of Probabilistic Computation and Linear Time. STOC 1997: 750

Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. Inf. Comput. 124(1): 1-6 (1996)

Stephen A. Fenner, Lance Fortnow, Lide Li: Gap-Definability as a Closure Property. Inf. Comput. 130(1): 1-17 (1996)

Lance Fortnow, Tomoyuki Yamakami: Generic Separations. J. Comput. Syst. Sci. 52(1): 191-197 (1996)

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: The Isomorphism Conjecture Holds Relative to an Oracle. SIAM J. Comput. 25(1): 193-206 (1996)

Stephen A. Fenner, Lance Fortnow, William I. Gasarch: Complexity Theory Newsflash. SIGACT News 27(3): 126 (1996)

Lance Fortnow, Martin Kummer: On Resource-Bounded Instance Complexity. Theor. Comput. Sci. 161(1&2): 123-140 (1996)

Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik: On Coherence, Random-self-reducibility, and Self-correction. IEEE Conference on Computational Complexity 1996: 59-67

Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney: L-Printable Sets. IEEE Conference on Computational Complexity 1996: 97-106

Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers: Inverting Onto Functions. IEEE Conference on Computational Complexity 1996: 213-222

Lance Fortnow, Sophie Laplante: Circuit Lower Bounds à la Kolmogorov. Inf. Comput. 123(1): 121-126 (1995)

Harry Buhrman, Lance Fortnow, Leen Torenvliet: Using Autoreducibility to Separate Complexity Classes. FOCS 1995: 520-527

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan: Measure, Category and Learning Theory. ICALP 1995: 558-569

Lance Fortnow, Martin Kummer: Resource-Bounded Instance Complexity (Extended Abstract). STACS 1995: 597-608

Stephen A. Fenner, Lance Fortnow: Beyond P^(NP) - NEXP. STACS 1995: 619-627

Lance Fortnow, William I. Gasarch, Sanjay Jain, Efim B. Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkovich, Theodore A. Slaman, Robert Solovay, Frank Stephan: Extremes in the Degrees of Inferability. Ann. Pure Appl. Logic 66(3): 231-276 (1994)

Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman: The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. Computational Complexity 4: 158-174 (1994)

Lance Fortnow: The Role of Relativization in Complexity Theory. Bulletin of the EATCS 52: 229-243 (1994)

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. J. Comput. Syst. Sci. 48(1): 116-148 (1994)

Lance Fortnow, Stuart A. Kurtz, Duke Whang: The infinite version of an open communication complexity problem is independent of the axioms of set theory. SIGACT News 25(1): 87-89 (1994)

Lance Fortnow, John Rompel, Michael Sipser: On the Power of Multi-Prover Interactive Protocols. Theor. Comput. Sci. 134(2): 545-557 (1994)

Lance Fortnow, Tomoyuki Yamakami: Generic Separations. Structure in Complexity Theory Conference 1994: 139-145

Lance Fortnow: My Favorite Ten Complexity Theorems of the Past Decade. FSTTCS 1994: 256-275

Lance Fortnow, John D. Rogers: Separability and One-Way Functions. ISAAC 1994: 396-404

Lance Fortnow, Duke Whang: Optimality and domination in repeated games with bounded players. STOC 1994: 741-749

Lance Fortnow: My Favorite Ten Complexity Theorems of the Past Decade. Electronic Colloquium on Computational Complexity (ECCC) 1(21) (1994)

László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson: BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Computational Complexity 3: 307-318 (1993)

Joan Feigenbaum, Lance Fortnow: Random-Self-Reducibility of Complete Sets. SIAM J. Comput. 22(5): 994-1005 (1993)

Lance Fortnow, Carsten Lund: Interactive Proof Systems and Alternating Time-Space Complexity. Theor. Comput. Sci. 113(1): 55-73 (1993)

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li: An Oarcle Builder's Toolkit. Structure in Complexity Theory Conference 1993: 120-131

Stephen A. Fenner, Lance Fortnow, Lide Li: Gap-Definability as a Closure Property. STACS 1993: 484-493

László Babai, Lance Fortnow, Carsten Lund: Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 2: 374 (1992)

Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992)

Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan: Algebraic Methods for Interactive Proof Systems. J. ACM 39(4): 859-868 (1992)

Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman: The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. Structure in Complexity Theory Conference 1992: 338-346

Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman: Degrees of Inferability. COLT 1992: 180-192

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: The Isomorphism Conjecture Holds Relative to an Oracle. FOCS 1992: 30-39

László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1: 3-40 (1991)

László Babai, Lance Fortnow: Arithmetization: A New Method in Structural Complexity Theory. Computational Complexity 1: 41-66 (1991)

Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. ASIACRYPT 1991: 346-351

Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. Structure in Complexity Theory Conference 1991: 13-15

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. Structure in Complexity Theory Conference 1991: 30-42

Joan Feigenbaum, Lance Fortnow: On the Random-Self-Reducibility of Complete Sets. Structure in Complexity Theory Conference 1991: 124-132

Lance Fortnow, Carsten Lund: Interactive Proof Systems and Alternating Time-Space Complexity. STACS 1991: 263-274

László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time. STOC 1991: 21-31

Lance Fortnow, John Rompel, Michael Sipser: Errata for On the Power of Multi-Prover Interactive Protocols. Structure in Complexity Theory Conference 1990: 318-319

Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan: Algebraic Methods for Interactive Proof Systems. FOCS 1990: 2-10

László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. FOCS 1990: 16-25

László Babai, Lance Fortnow: A Characterization of \sharp P Arithmetic Straight Line Programs. FOCS 1990: 26-34

Lance Fortnow, Michael Sipser: Probabilistic Computation and Linear Time. STOC 1989: 148-156

Lance Fortnow, Michael Sipser: Are There Interactive Protocols for CO-NP Languages? Inf. Process. Lett. 28(5): 249-251 (1988)

Lance Fortnow, John Rompel, Michael Sipser: On the power of multi-power interactive protocols. Structure in Complexity Theory Conference 1988: 156-161

Lance Fortnow: The complexity of perfect zero-knowledge. Structure in Complexity Theory Conference 1987

Lance Fortnow: The Complexity of Perfect Zero-Knowledge (Extended Abstract). STOC 1987: 204-209