


default search action
Lance Fortnow
Person information
- affiliation: Illinois Institute of Technology, Chicago, IL, USA
- affiliation: Georgia Institute of Technology, Atlanta, USA
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2013
- [b1]Lance Fortnow:
The Golden Ticket - P, NP, and the Search for the Impossible. Princeton University Press 2013, ISBN 978-0-691-15649-1, pp. I-X, 1-176
Journal Articles
- 2022
- [j82]Lance Fortnow:
Fifty years of P vs. NP and the possibility of the impossible. Commun. ACM 65(1): 76-85 (2022) - [j81]Lance Fortnow:
Computational Complexity. Bull. EATCS 136 (2022) - 2021
- [j80]Lance Fortnow:
Worlds to Die Harder For Open Oracle Questions for the 21st Century. SIGACT News 52(3): 26-36 (2021) - 2017
- [j79]Lance Fortnow, Rahul Santhanam:
Robust simulations and significant separations. Inf. Comput. 256: 149-159 (2017) - 2016
- [j78]Lance Fortnow:
David Stifler Johnson: A Tribute by Lance Fortnow. Bull. EATCS 119 (2016) - [j77]Lance Fortnow:
The Golden Ticket P, NP, and the Search for the Impossible. Bull. EATCS 120 (2016) - 2013
- [j76]Tugkan Batu
, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. J. ACM 60(1): 4:1-4:25 (2013) - 2012
- [j75]Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
:
Low-Depth Witnesses are Easy to Find. Comput. Complex. 21(3): 479-497 (2012) - [j74]Lance Fortnow:
The Enduring Legacy of the Turing Machine. Comput. J. 55(7): 830-831 (2012) - [j73]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
:
Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51(2): 229-247 (2012) - 2011
- [j72]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) - [j71]Lance Fortnow, Joshua A. Grochow:
Complexity classes of equivalence problems revisited. Inf. Comput. 209(4): 748-763 (2011) - [j70]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011) - 2010
- [j69]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) - [j68]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) - [j67]Lance Fortnow:
Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine. Ubiquity 2010(December): 5 (2010) - 2009
- [j66]Lance Fortnow:
Viewpoint - Time for computer science to grow up. Commun. ACM 52(8): 33-35 (2009) - [j65]Lance Fortnow:
The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) - [j64]Lance Fortnow, Adam R. Klivans:
Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75(1): 27-36 (2009) - [j63]Luis Filipe Coelho Antunes, Lance Fortnow:
Sophistication Revisited. Theory Comput. Syst. 45(1): 150-161 (2009) - [j62]Lance Fortnow:
A Simple Proof of Toda's Theorem. Theory Comput. 5(1): 135-140 (2009) - [j61]Lance Fortnow:
Editor's Foreword. ACM Trans. Comput. Theory 1(1): 1:1-1:2 (2009) - 2008
- [j60]Lance Fortnow, Russell Impagliazzo
, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17(3): 353-376 (2008) - [j59]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) - [j58]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008) - [j57]Lance Fortnow, Rakesh V. Vohra:
The complexity of forecast testing. SIGecom Exch. 7(3) (2008) - 2007
- [j56]Yiling Chen, Lance Fortnow, Evdokia Nikolova
, David M. Pennock:
Combinatorial betting. SIGecom Exch. 7(1): 61-64 (2007) - 2006
- [j55]Richard Beigel, Lance Fortnow, William I. Gasarch:
A tight lower bound for restricted pir protocols. Comput. Complex. 15(1): 82-91 (2006) - [j54]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) - [j53]Richard Beigel, Lance Fortnow, Frank Stephan
:
Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006) - [j52]Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran:
Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006) - [j51]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. Theory Comput. 2(9): 173-183 (2006) - 2005
- [j50]Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman
:
Betting Boolean-style: a framework for trading in securities based on logical formulas. Decis. Support Syst. 39(1): 87-104 (2005) - [j49]Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas:
Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005) - [j48]Lance Fortnow, Jack H. Lutz:
Prediction and dimension. J. Comput. Syst. Sci. 70(4): 570-589 (2005) - [j47]Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005) - [j46]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) - [j45]Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami:
Computation in a distributed information market. Theor. Comput. Sci. 343(1-2): 114-132 (2005) - 2004
- [j44]Lance Fortnow:
Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. SIGACT News 35(2): 16-18 (2004) - 2003
- [j43]Lance Fortnow, Steven Homer:
A Short History of Computational Complexity. Bull. EATCS 80: 95-133 (2003) - [j42]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li:
An oracle builder's toolkit. Inf. Comput. 182(2): 95-136 (2003) - [j41]Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers:
Inverting onto functions. Inf. Comput. 186(1): 90-103 (2003) - [j40]Lance Fortnow:
One complexity theorist's view of quantum computing. Theor. Comput. Sci. 292(3): 597-610 (2003) - [j39]Rodney G. Downey, Lance Fortnow:
Uniformly hard languages. Theor. Comput. Sci. 298(2): 303-315 (2003) - 2002
- [j38]Lance Fortnow, John D. Rogers:
Separability and one-way functions. Comput. Complex. 11(3-4): 137-157 (2002) - 2001
- [j37]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet:
Two oracles that force a big crunch. Comput. Complex. 10(2): 93-116 (2001) - [j36]Lance Fortnow:
Guest Editor's Foreword. J. Comput. Syst. Sci. 62(2): 215 (2001) - [j35]Lance Fortnow, Aduri Pavan, Alan L. Selman:
Distributionally Hard Languages. Theory Comput. Syst. 34(3): 245-261 (2001) - [j34]Harry Buhrman, Lance Fortnow, Sophie Laplante:
Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. 31(3): 887-905 (2001) - 2000
- [j33]Lance Fortnow:
Diagonalization. Bull. EATCS 71: 102-113 (2000) - [j32]Lance Fortnow:
Time-Space Tradeoffs for Satisfiability. J. Comput. Syst. Sci. 60(2): 337-353 (2000) - [j31]Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000) - 1999
- [j30]Lance Fortnow:
Relativized Worlds with an Infinite Hierarchy. Inf. Process. Lett. 69(6): 309-313 (1999) - [j29]Harry Buhrman, Lance Fortnow:
Two Queries. J. Comput. Syst. Sci. 59(2): 182-194 (1999) - [j28]Lance Fortnow, John D. Rogers:
Complexity Limitations on Quantum Computation. J. Comput. Syst. Sci. 59(2): 240-252 (1999) - [j27]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) - 1998
- [j26]Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik:
On Coherence, Random-Self-Reducibility, and Self-Correction. Comput. Complex. 7(2): 174-191 (1998) - [j25]Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney:
L-Printable Sets. SIAM J. Comput. 28(1): 137-151 (1998) - [j24]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) - 1996
- [j23]Lance Fortnow, Nick Reingold:
PP is Closed Under Truth-Table Reductions. Inf. Comput. 124(1): 1-6 (1996) - [j22]Stephen A. Fenner, Lance Fortnow, Lide Li:
Gap-Definability as a Closure Property. Inf. Comput. 130(1): 1-17 (1996) - [j21]Lance Fortnow, Tomoyuki Yamakami:
Generic Separations. J. Comput. Syst. Sci. 52(1): 191-197 (1996) - [j20]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle. SIAM J. Comput. 25(1): 193-206 (1996) - [j19]Stephen A. Fenner, Lance Fortnow, William I. Gasarch:
Complexity Theory Newsflash. SIGACT News 27(3): 126 (1996) - [j18]Lance Fortnow, Martin Kummer:
On Resource-Bounded Instance Complexity. Theor. Comput. Sci. 161(1&2): 123-140 (1996) - 1995
- [j17]Lance Fortnow, Sophie Laplante:
Circuit Lower Bounds à la Kolmogorov. Inf. Comput. 123(1): 121-126 (1995) - 1994
- [j16]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. Log. 66(3): 231-276 (1994) - [j15]Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman
:
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. Comput. Complex. 4: 158-174 (1994) - [j14]Lance Fortnow:
The Role of Relativization in Complexity Theory. Bull. EATCS 52: 229-243 (1994) - [j13]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
Gap-Definable Counting Classes. J. Comput. Syst. Sci. 48(1): 116-148 (1994) - [j12]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) - [j11]Lance Fortnow, John Rompel, Michael Sipser:
On the Power of Multi-Prover Interactive Protocols. Theor. Comput. Sci. 134(2): 545-557 (1994) - 1993
- [j10]László Babai
, Lance Fortnow, Noam Nisan, Avi Wigderson:
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs. Comput. Complex. 3: 307-318 (1993) - [j9]Joan Feigenbaum, Lance Fortnow:
Random-Self-Reducibility of Complete Sets. SIAM J. Comput. 22(5): 994-1005 (1993) - [j8]Lance Fortnow, Carsten Lund:
Interactive Proof Systems and Alternating Time-Space Complexity. Theor. Comput. Sci. 113(1): 55-73 (1993) - 1992
- [j7]László Babai
, Lance Fortnow, Carsten Lund:
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 2: 374 (1992) - [j6]Lance Fortnow, Mario Szegedy:
On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992) - [j5]Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems. J. ACM 39(4): 859-868 (1992) - 1991
- [j4]László Babai
, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Comput. Complex. 1: 3-40 (1991) - [j3]László Babai
, Lance Fortnow:
Arithmetization: A New Method in Structural Complexity Theory. Comput. Complex. 1: 41-66 (1991) - 1989
- [j2]Lance Fortnow:
The Complexity of Perfect Zero-Knowledge. Adv. Comput. Res. 5: 327-343 (1989) - 1988
- [j1]Lance Fortnow, Michael Sipser:
Are There Interactive Protocols for CO-NP Languages? Inf. Process. Lett. 28(5): 249-251 (1988)
Conference and Workshop Papers
- 2018
- [c103]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching. IEEE CLOUD 2018: 426-433 - [c102]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching. CLOUD 2018: 69-83 - [c101]Liang Liu, Jun (Jim) Xu, Lance Fortnow:
Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks. UCC 2018: 237-246 - 2017
- [c100]Lance Fortnow:
Complexity with Rod. Computability and Complexity 2017: 115-121 - 2016
- [c99]Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu:
Randomized Algorithms for Dynamic Storage Load-Balancing. SoCC 2016: 210-222 - [c98]Lance Fortnow, Rahul Santhanam
:
New Non-Uniform Lower Bounds for Uniform Classes. CCC 2016: 19:1-19:14 - [c97]Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu:
Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing. SIGMETRICS 2016: 381-382 - 2015
- [c96]Lance Fortnow:
Nondeterministic Separations. TAMC 2015: 10-17 - 2013
- [c95]Lance Fortnow:
A Personal View of the P versus NP Problem. CiE 2013: 147-148 - [c94]Harry Buhrman, Lance Fortnow, John M. Hitchcock
, Bruno Loff
:
Learning Reductions to Sparse Sets. MFCS 2013: 243-253 - 2011
- [c93]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580 - [c92]Michele Budinich, Lance Fortnow:
Repeated matching pennies with limited randomness. EC 2011: 111-118 - 2010
- [c91]Harry Buhrman, Lance Fortnow, Michal Koucký
, Bruno Loff
:
Derandomizing from Random Strings. CCC 2010: 58-63 - [c90]Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. ICS 2010: 143-155 - [c89]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo
:
Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS 2010: 395-404 - 2009
- [c88]Lance Fortnow, Rahul Santhanam, Ryan Williams
:
Fixed-Polynomial Size Circuit Bounds. CCC 2009: 19-26 - [c87]Luis Filipe Coelho Antunes, Lance Fortnow:
Worst-Case Running Times for Average-Case Algorithms. CCC 2009: 298-303 - [c86]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209 - [c85]Nikhil R. Devanur, Lance Fortnow:
A computational theory of awareness and decision making. TARK 2009: 99-107 - [c84]Lance Fortnow:
Program equilibria and discounted computation time. TARK 2009: 128-133 - 2008
- [c83]Lance Fortnow, Rakesh Vohra:
The complexity of forecast testing: abstract. EC 2008: 139 - [c82]Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman:
Complexity of combinatorial market makers. EC 2008: 190-199 - [c81]Lance Fortnow, Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142 - 2007
- [c80]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
:
Low-Depth Witnesses are Easy to Find. CCC 2007: 46-51 - [c79]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103 - [c78]Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock:
Betting on permutations. EC 2007: 326-335 - [c77]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 - 2006
- [c76]Lance Fortnow, Adam R. Klivans:
Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363 - [c75]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 - [c74]Lance Fortnow, Mitsunori Ogihara
:
Very Sparse Leaf Languages. MFCS 2006: 375-386 - [c73]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. STACS 2006: 137-148 - [c72]Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. STACS 2006: 469-476 - 2005
- [c71]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. CCC 2005: 135-140 - [c70]Lance Fortnow, Adam R. Klivans:
NP with Small Advice. CCC 2005: 228-234 - [c69]Lance Fortnow, Russell Impagliazzo
, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. CCC 2005: 323-332 - [c68]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. STACS 2005: 412-421 - [c67]Lance Fortnow:
Beyond NP: the work and legacy of Larry Stockmeyer. STOC 2005: 120-127 - [c66]Lance Fortnow, Rahul Santhanam, Luca Trevisan
:
Hierarchies for semantic classes. STOC 2005: 348-355 - 2004
- [c65]Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324 - 2003
- [c64]Richard Beigel, Lance Fortnow:
Are Cook and Karp Ever the Same? CCC 2003: 333-336 - [c63]Lance Fortnow, Aduri Pavan, Samik Sengupta:
Proving SAT does not have Small Circuits with an Application to the Two. CCC 2003: 347- - [c62]Luis Antunes, Lance Fortnow, N. V. Vinodchandran:
Using Depth to Capture Average-Case Complexity. FCT 2003: 303-310 - [c61]