default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDLance 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]Luis Antunes, Lance Fortnow:
Sophistication Revisited. ICALP 2003: 267-277 - [c60]Richard Beigel, Lance Fortnow, Frank Stephan:
Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107 - [c59]Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman:
Betting boolean-style: a framework for trading in securities based on logical formulas. EC 2003: 144-155 - [c58]Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami:
Computation in a distributed information market. EC 2003: 156-165 - [c57]Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig:
Quantum property testing. SODA 2003: 480-488 - [c56]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 - [c55]Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. STACS 2003: 212-222 - [c54]Harry Buhrman, Richard Chang, Lance Fortnow:
One Bit of Advice. STACS 2003: 547-558 - 2002
- [c53]Lance Fortnow:
The History of Complexity. CCC 2002: 61 - [c52]Lance Fortnow, Jack H. Lutz:
Prediction and Dimension. COLT 2002: 380-395 - 2001
- [c51]Lance Fortnow:
Comparing Notions of Full Derandomization. CCC 2001: 28-34 - [c50]Luis Antunes, Lance Fortnow, Dieter van Melkebeek:
Computational Depth. CCC 2001: 266-273 - [c49]Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White:
Testing Random Variables for Independence and Identity. FOCS 2001: 442-451 - [c48]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 - 2000
- [c47]Lance Fortnow, Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation. CCC 2000: 2-13 - [c46]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing that distributions are close. FOCS 2000: 259-269 - [c45]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek:
Optimal Proof Systems and Sparse Sets. STACS 2000: 407-418 - [c44]Lance Fortnow:
One complexity theorist's view of quantum computing. CATS 2000: 58-72 - 1999
- [c43]Lance Fortnow, Aduri Pavan, Alan L. Selman:
Distributionally-Hard Languages. COCOON 1999: 184-193 - [c42]Harry Buhrman, Lance Fortnow:
One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109 - 1998
- [c41]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Nonrelativizing Separations. CCC 1998: 8-12 - [c40]Harry Buhrman, Lance Fortnow:
Two Queries. CCC 1998: 13- - [c39]Lance Fortnow, John D. Rogers:
Complexity Limitations on Quantum Computation. CCC 1998: 202-209 - [c38]Rodney G. Downey, Lance Fortnow:
Uniformly Hard Languages. CCC 1998: 228- - [c37]Lance Fortnow, Sophie Laplante:
Nearly Optimal Language Compression Using Extractors. STACS 1998: 84-93 - [c36]Richard Beigel, Harry Buhrman, Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208 - [c35]Lance Fortnow, Peter G. Kimmel:
Beating a Finite Automaton in the Big Match. TARK 1998: 225-234 - 1997
- [c34]Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Six Hypotheses in Search of a Theorem. CCC 1997: 2-12 - [c33]Lance Fortnow:
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. CCC 1997: 52-60 - [c32]Harry Buhrman, Stephen A. Fenner, Lance Fortnow:
Results on Resource-Bounded Measure. ICALP 1997: 188-194 - [c31]Harry Buhrman, Lance Fortnow:
Resource-Bounded Kolmogorov Complexity Revisited. STACS 1997: 105-116 - [c30]Lance Fortnow, Michael Sipser:
Retraction of Probabilistic Computation and Linear Time. STOC 1997: 750 - 1996
- [c29]Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik:
On Coherence, Random-self-reducibility, and Self-correction. CCC 1996: 59-67 - [c28]Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney:
L-Printable Sets. CCC 1996: 97-106 - [c27]Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers:
Inverting Onto Functions. CCC 1996: 213-222 - 1995
- [c26]Harry Buhrman, Lance Fortnow, Leen Torenvliet:
Using Autoreducibility to Separate Complexity Classes. FOCS 1995: 520-527 - [c25]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 - [c24]Lance Fortnow, Martin Kummer:
Resource-Bounded Instance Complexity (Extended Abstract). STACS 1995: 597-608 - [c23]Stephen A. Fenner, Lance Fortnow:
Beyond P^(NP) - NEXP. STACS 1995: 619-627 - 1994
- [c22]Lance Fortnow, Tomoyuki Yamakami:
Generic Separations. SCT 1994: 139-145 - [c21]Lance Fortnow:
My Favorite Ten Complexity Theorems of the Past Decade. FSTTCS 1994: 256-275 - [c20]Lance Fortnow, John D. Rogers:
Separability and One-Way Functions. ISAAC 1994: 396-404 - [c19]Lance Fortnow, Duke Whang:
Optimality and domination in repeated games with bounded players. STOC 1994: 741-749 - 1993
- [c18]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li:
An Oarcle Builder's Toolkit. SCT 1993: 120-131 - [c17]Stephen A. Fenner, Lance Fortnow, Lide Li:
Gap-Definability as a Closure Property. STACS 1993: 484-493 - 1992
- [c16]Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman:
The Power of Adaptiveness and Additional Queries in Random-Self-Reductions. SCT 1992: 338-346 - [c15]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 - [c14]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle. FOCS 1992: 30-39 - 1991
- [c13]Lance Fortnow, Mario Szegedy:
On the Power of Two-Local Random Reductions. ASIACRYPT 1991: 346-351 - [c12]Lance Fortnow, Nick Reingold:
PP is Closed Under Truth-Table Reductions. SCT 1991: 13-15 - [c11]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz:
Gap-Definable Counting Classes. SCT 1991: 30-42 - [c10]Joan Feigenbaum, Lance Fortnow:
On the Random-Self-Reducibility of Complete Sets. SCT 1991: 124-132 - [c9]Lance Fortnow, Carsten Lund:
Interactive Proof Systems and Alternating Time-Space Complexity. STACS 1991: 263-274 - [c8]László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy:
Checking Computations in Polylogarithmic Time. STOC 1991: 21-31 - 1990
- [c7]Lance Fortnow, John Rompel, Michael Sipser:
Errata for On the Power of Multi-Prover Interactive Protocols. SCT 1990: 318-319 - [c6]Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems. FOCS 1990: 2-10 - [c5]László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. FOCS 1990: 16-25 - [c4]László Babai, Lance Fortnow:
A Characterization of \sharp P Arithmetic Straight Line Programs. FOCS 1990: 26-34 - 1988
- [c3]Lance Fortnow, John Rompel, Michael Sipser:
On the power of multi-power interactive protocols. SCT 1988: 156-161 - 1987
- [c2]Lance Fortnow:
The complexity of perfect zero-knowledge. SCT 1987: 156 - [c1]Lance Fortnow:
The Complexity of Perfect Zero-Knowledge (Extended Abstract). STOC 1987: 204-209
Parts in Books or Collections
- 2001
- [p1]Lance Fortnow:
Diagonalization. Current Trends in Theoretical Computer Science 2001: 102-114
Editorship
- 2011
- [e6]Lance Fortnow, Salil P. Vadhan:
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 [contents] - 2009
- [e5]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009. Dagstuhl Seminar Proceedings 09421, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [e4]John Chuang, Lance Fortnow, Pearl Pu:
Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009. ACM 2009, ISBN 978-1-60558-458-4 [contents] - 2008
- [e3]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
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 [contents] - [e2]Lance Fortnow, John Riedl, Tuomas Sandholm:
Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008. ACM 2008, ISBN 978-1-60558-169-9 [contents] - 2005
- [e1]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Algebraic Methods in Computational Complexity, 10.-15. October 2004. Dagstuhl Seminar Proceedings 04421, IBFI, Schloss Dagstuhl, Germany 2005 [contents]
Reference Works
- 2014
- [r1]Lance Fortnow, Steven Homer:
Computational Complexity. Computational Logic 2014: 495-521
Informal and Other Publications
- 2020
- [i41]C. N. P. Slagle, Lance Fortnow:
Matrix Multiplication and Binary Space Partitioning Trees : An Exploration. CoRR abs/2012.05365 (2020) - 2017
- [i40]Stephen A. Fenner, Lance Fortnow:
Compression Complexity. CoRR abs/1702.04779 (2017) - [i39]Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow:
Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers. CoRR abs/1712.06634 (2017) - 2014
- [i38]Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. Electron. Colloquium Comput. Complex. TR14 (2014) - 2012
- [i37]Lance Fortnow, Rahul Sami:
Multi-outcome and Multidimensional Market Scoring Rules. CoRR abs/1202.1712 (2012) - 2011
- [i36]Michele Budinich, Lance Fortnow:
Repeated Matching Pennies with Limited Randomness. CoRR abs/1102.1096 (2011) - 2010
- [i35]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White:
Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010) - [i34]Lance Fortnow, Rahul Santhanam:
Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010) - 2009
- [i33]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i32]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i31]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Algebraic Methods in Computational Complexity 2009 - [i30]Lance Fortnow, Joshua A. Grochow:
Complexity Classes of Equivalence Problems Revisited. CoRR abs/0907.4775 (2009) - [i29]Lance Fortnow, Rahul Santhanam:
Bounding Rationality by Discounting Time. CoRR abs/0911.3162 (2009) - [i28]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings. CoRR abs/0912.3162 (2009) - [i27]Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [i26]Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman:
Complexity of Combinatorial Market Makers. CoRR abs/0802.1362 (2008) - [i25]Nikhil R. Devanur, Lance Fortnow:
A Computational Theory of Awareness and Decision Making. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [i24]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i23]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf:
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007 - [i22]Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey. Electron. Colloquium Comput. Complex. TR07 (2007) - [i21]Lance Fortnow, Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i20]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
Low-Depth Witnesses are Easy to Find. Electron. Colloquium Comput. Complex. TR06 (2006) - [i19]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
Inverting onto functions might not be hard. Electron. Colloquium Comput. Complex. TR06 (2006) - [i18]Lance Fortnow, Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds. Electron. Colloquium Comput. Complex. TR06 (2006) - [i17]Lance Fortnow, Rakesh Vohra:
The Complexity of Forecast Testing. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [i16]Lance Fortnow, Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space. Electron. Colloquium Comput. Complex. TR05 (2005) - [i15]Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. Electron. Colloquium Comput. Complex. TR05 (2005) - [i14]Lance Fortnow, Luis Antunes:
Time-Bounded Universal Distributions. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [i13]Harry Buhrman, Lance Fortnow, Thomas Thierauf:
04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004 - [i12]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the complexity of succinct zero-sum games. Electron. Colloquium Comput. Complex. TR04 (2004) - [i11]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. Electron. Colloquium Comput. Complex. TR04 (2004) - [i10]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. Electron. Colloquium Comput. Complex. TR04 (2004) - [i9]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR04 (2004) - [i8]Lance Fortnow, Rahul Santhanam, Luca Trevisan:
Promise Hierarchies. Electron. Colloquium Comput. Complex. TR04 (2004) - [i7]Lance Fortnow, Adam R. Klivans:
NP with Small Advice. Electron. Colloquium Comput. Complex. TR04 (2004) - [i6]Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [i5]Richard Beigel, Lance Fortnow, William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols. Electron. Colloquium Comput. Complex. TR03 (2003) - 2000
- [i4]Lance Fortnow:
One Complexity Theorist's View of Quantum Computing. CoRR quant-ph/0003035 (2000) - [i3]Lance Fortnow, Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation. Electron. Colloquium Comput. Complex. TR00 (2000) - 1998
- [i2]Lance Fortnow, John D. Rogers:
Complexity limitations on quantum computation. CoRR cs.CC/9811023 (1998) - 1994
- [i1]Lance Fortnow:
My Favorite Ten Complexity Theorems of the Past Decade. Electron. Colloquium Comput. Complex. TR94 (1994)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:20 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
