Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Lance Fortnow
2010 – today
- 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- [j75]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. J. ACM 60(1): 4 (2013)
- [c98]
- [c97]Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff: Learning Reductions to Sparse Sets. MFCS 2013: 243-253
- 2012
- [j74]Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Computational Complexity 21(3): 479-497 (2012)
- [j73]
- [j72]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51(2): 229-247 (2012)
- [i31]Lance Fortnow, Rahul Sami: Multi-outcome and Multidimensional Market Scoring Rules. CoRR abs/1202.1712 (2012)
- 2011
- [j71]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)
- [j70]Lance Fortnow, Joshua A. Grochow: Complexity classes of equivalence problems revisited. Inf. Comput. 209(4): 748-763 (2011)
- [j69]Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)
- [c96]Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580
- [c95]Michele Budinich, Lance Fortnow: Repeated matching pennies with limited randomness. ACM Conference on Electronic Commerce 2011: 111-118
- [e5]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
- [i30]Michele Budinich, Lance Fortnow: Repeated Matching Pennies with Limited Randomness. CoRR abs/1102.1096 (2011)
- 2010
- [j68]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)
- [j67]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)
- [c94]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. IEEE Conference on Computational Complexity 2010: 58-63
- [c93]
- [c92]Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS 2010: 395-404
- [i29]Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions. CoRR abs/1009.5397 (2010)
- [i28]Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations. CoRR abs/1012.2034 (2010)
2000 – 2009
- 2009
- [j66]
- [j65]
- [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]
- [j61]
- [c91]Lance Fortnow, Rahul Santhanam, Ryan Williams: Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26
- [c90]Luis Filipe Coelho Antunes, Lance Fortnow: Worst-Case Running Times for Average-Case Algorithms. IEEE Conference on Computational Complexity 2009: 298-303
- [c89]Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209
- [c88]Nikhil R. Devanur, Lance Fortnow: A computational theory of awareness and decision making. TARK 2009: 99-107
- [c87]
- [e4]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
- [i27]Lance Fortnow, Joshua A. Grochow: Complexity Classes of Equivalence Problems Revisited. CoRR abs/0907.4775 (2009)
- [i26]
- [i25]Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. CoRR abs/0912.3162 (2009)
- [i24]Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009)
- 2008
- [j60]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 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]
- [c86]Lance Fortnow, Rakesh Vohra: The complexity of forecast testing: abstract. ACM Conference on Electronic Commerce 2008: 139
- [c85]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
- [c84]Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142
- [e3]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
- [e2]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
- [i23]Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of Combinatorial Market Makers. CoRR abs/0802.1362 (2008)
- [i22]Nikhil R. Devanur, Lance Fortnow: A Computational Theory of Awareness and Decision Making. Electronic Colloquium on Computational Complexity (ECCC) 15(046) (2008)
- 2007
- [j56]Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Combinatorial betting. SIGecom Exchanges 7(1): 61-64 (2007)
- [c83]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. IEEE Conference on Computational Complexity 2007: 46-51
- [c82]Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
- [c81]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c80]Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
- [c79]Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Betting on permutations. ACM Conference on Electronic Commerce 2007: 326-335
- [c78]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
- [i21]Lance Fortnow, Rahul Santhanam: Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004) (2007)
- [i20]Lance Fortnow, Rahul Santhanam: Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096) (2007)
- 2006
- [j55]Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 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 of Computing 2(1): 173-183 (2006)
- [c77]Lance Fortnow, Adam R. Klivans: Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363
- [c76]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
- [c75]
- [c74]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
- [c73]
- [i19]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)
- [i18]Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Electronic Colloquium on Computational Complexity (ECCC) 13(125) (2006)
- [i17]Lance Fortnow, Rakesh Vohra: The Complexity of Forecast Testing. Electronic Colloquium on Computational Complexity (ECCC) 13(149) (2006)
- [i16]Lance Fortnow, Rahul Santhanam: Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157) (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. Decision Support Systems 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]
- [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)
- [c72]Eldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. IEEE Conference on Computational Complexity 2005: 135-140
- [c71]Lance Fortnow, Adam R. Klivans: NP with Small Advice. IEEE Conference on Computational Complexity 2005: 228-234
- [c70]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. IEEE Conference on Computational Complexity 2005: 323-332
- [c69]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
- [c68]
- [c67]
- [e1]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
- [i15]Lance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space. Electronic Colloquium on Computational Complexity (ECCC)(042) (2005)
- [i14]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)
- [i13]Lance Fortnow, Luis Antunes: Time-Bounded Universal Distributions. Electronic Colloquium on Computational Complexity (ECCC)(144) (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)
- [c66]Harry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004
- [c65]Lance Fortnow, Rahul Santhanam: Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324
- [i12]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the complexity of succinct zero-sum games. Electronic Colloquium on Computational Complexity (ECCC)(001) (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. Electronic Colloquium on Computational Complexity (ECCC)(015) (2004)
- [i10]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. Electronic Colloquium on Computational Complexity (ECCC)(080) (2004)
- [i9]Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. Electronic Colloquium on Computational Complexity (ECCC)(081) (2004)
- [i8]Lance Fortnow, Rahul Santhanam, Luca Trevisan: Promise Hierarchies. Electronic Colloquium on Computational Complexity (ECCC)(098) (2004)
- [i7]Lance Fortnow, Adam R. Klivans: NP with Small Advice. Electronic Colloquium on Computational Complexity (ECCC)(103) (2004)
- [i6]Eldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. Electronic Colloquium on Computational Complexity (ECCC)(105) (2004)
- 2003
- [j43]Lance Fortnow, Steven Homer: A Short History of Computational Complexity. Bulletin of the 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]Rodney G. Downey, Lance Fortnow: Uniformly hard languages. Theor. Comput. Sci. 2(298): 303-315 (2003)
- [j39]Lance Fortnow: One complexity theorist's view of quantum computing. Theor. Comput. Sci. 292(3): 597-610 (2003)
- [c64]Richard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336
- [c63]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-
- [c62]Luis Antunes, Lance Fortnow, N. V. Vinodchandran: Using Depth to Capture Average-Case Complexity. FCT 2003: 303-310
- [c61]
- [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. ACM Conference on Electronic Commerce 2003: 144-155
- [c58]Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami: Computation in a distributed information market. ACM Conference on Electronic Commerce 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]
- [c54]
- [i5]Richard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols. Electronic Colloquium on Computational Complexity (ECCC)(087) (2003)
- 2002
- [j38]Lance Fortnow, John D. Rogers: Separability and one-way functions. Computational Complexity 11(3-4): 137-157 (2002)
- [c53]
- [c52]
- 2001
- [j37]Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet: Two oracles that force a big crunch. Computational Complexity 10(2): 93-116 (2001)
- [j36]
- [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)
- [c51]Lance Fortnow: Comparing Notions of Full Derandomization. IEEE Conference on Computational Complexity 2001: 28-34
- [c50]Luis Antunes, Lance Fortnow, Dieter van Melkebeek: Computational Depth. IEEE Conference on Computational Complexity 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
- [p1]
- 2000
- [j33]
- [j32]
- [j31]Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet: Separating Complexity Classes Using Autoreducibility. SIAM J. Comput. 29(5): 1497-1520 (2000)
- [j30]Lance Fortnow: One complexity theorist's view of quantum computing. Electr. Notes Theor. Comput. Sci. 31: 58-72 (2000)
- [c47]Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 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
- [i4]
- [i3]Lance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. Electronic Colloquium on Computational Complexity (ECCC) 7(28) (2000)
1990 – 1999
- 1999
- [j29]Lance Fortnow: Relativized Worlds with an Infinite Hierarchy. Inf. Process. Lett. 69(6): 309-313 (1999)
- [j28]
- [j27]Lance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. J. Comput. Syst. Sci. 59(2): 240-252 (1999)
- [j26]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)
- [c44]
- [c43]Harry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109
- 1998
- [j25]Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik: On Coherence, Random-Self-Reducibility, and Self-Correction. Computational Complexity 7(2): 174-191 (1998)
- [j24]Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney: L-Printable Sets. SIAM J. Comput. 28(1): 137-151 (1998)
- [j23]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)
- [c42]Harry Buhrman, Lance Fortnow, Thomas Thierauf: Nonrelativizing Separations. IEEE Conference on Computational Complexity 1998: 8-12
- [c41]
- [c40]Lance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. IEEE Conference on Computational Complexity 1998: 202-209
- [c39]Rodney G. Downey, Lance Fortnow: Uniformly Hard Languages. IEEE Conference on Computational Complexity 1998: 228-
- [c38]Lance Fortnow, Sophie Laplante: Nearly Optimal Language Compression Using Extractors. STACS 1998: 84-93
- [c37]Richard Beigel, Harry Buhrman, Lance Fortnow: NP Might Not Be As Easy As Detecting Unique Solutions. STOC 1998: 203-208
- [c36]
- [i2]Lance Fortnow, John D. Rogers: Complexity limitations on quantum computation. CoRR cs.CC/9811023 (1998)
- 1997
- [c35]Harry Buhrman, Lance Fortnow, Leen Torenvliet: Six Hypotheses in Search of a Theorem. IEEE Conference on Computational Complexity 1997: 2-12
- [c34]Lance Fortnow: Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability. IEEE Conference on Computational Complexity 1997: 52-60
- [c33]Harry Buhrman, Stephen A. Fenner, Lance Fortnow: Results on Resource-Bounded Measure. ICALP 1997: 188-194
- [c32]
- [c31]Lance Fortnow, Michael Sipser: Retraction of Probabilistic Computation and Linear Time. STOC 1997: 750
- 1996
- [j22]Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. Inf. Comput. 124(1): 1-6 (1996)
- [j21]Stephen A. Fenner, Lance Fortnow, Lide Li: Gap-Definability as a Closure Property. Inf. Comput. 130(1): 1-17 (1996)
- [j20]
- [j19]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: The Isomorphism Conjecture Holds Relative to an Oracle. SIAM J. Comput. 25(1): 193-206 (1996)
- [j18]Stephen A. Fenner, Lance Fortnow, William I. Gasarch: Complexity Theory Newsflash. SIGACT News 27(3): 126 (1996)
- [j17]Lance Fortnow, Martin Kummer: On Resource-Bounded Instance Complexity. Theor. Comput. Sci. 161(1&2): 123-140 (1996)
- [c30]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
- [c29]Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney: L-Printable Sets. IEEE Conference on Computational Complexity 1996: 97-106
- [c28]Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers: Inverting Onto Functions. IEEE Conference on Computational Complexity 1996: 213-222
- 1995
- [j16]Lance Fortnow, Sophie Laplante: Circuit Lower Bounds à la Kolmogorov. Inf. Comput. 123(1): 121-126 (1995)
- [c27]Harry Buhrman, Lance Fortnow, Leen Torenvliet: Using Autoreducibility to Separate Complexity Classes. FOCS 1995: 520-527
- [c26]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
- [c25]Lance Fortnow, Martin Kummer: Resource-Bounded Instance Complexity (Extended Abstract). STACS 1995: 597-608
- [c24]
- 1994
- [j15]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)
- [j14]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)
- [j13]Lance Fortnow: The Role of Relativization in Complexity Theory. Bulletin of the EATCS 52: 229-243 (1994)
- [j12]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. J. Comput. Syst. Sci. 48(1): 116-148 (1994)
- [j11]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)
- [j10]Lance Fortnow, John Rompel, Michael Sipser: On the Power of Multi-Prover Interactive Protocols. Theor. Comput. Sci. 134(2): 545-557 (1994)
- [c23]Lance Fortnow, Tomoyuki Yamakami: Generic Separations. Structure in Complexity Theory Conference 1994: 139-145
- [c22]
- [c21]
- [c20]Lance Fortnow, Duke Whang: Optimality and domination in repeated games with bounded players. STOC 1994: 741-749
- [i1]Lance Fortnow: My Favorite Ten Complexity Theorems of the Past Decade. Electronic Colloquium on Computational Complexity (ECCC) 1(21) (1994)
- 1993
- [j9]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)
- [j8]Joan Feigenbaum, Lance Fortnow: Random-Self-Reducibility of Complete Sets. SIAM J. Comput. 22(5): 994-1005 (1993)
- [j7]Lance Fortnow, Carsten Lund: Interactive Proof Systems and Alternating Time-Space Complexity. Theor. Comput. Sci. 113(1): 55-73 (1993)
- [c19]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li: An Oarcle Builder's Toolkit. Structure in Complexity Theory Conference 1993: 120-131
- [c18]Stephen A. Fenner, Lance Fortnow, Lide Li: Gap-Definability as a Closure Property. STACS 1993: 484-493
- 1992
- [j6]László Babai, Lance Fortnow, Carsten Lund: Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 2: 374 (1992)
- [j5]Lance Fortnow, Mario Szegedy: On the Power of Two-Local Random Reductions. Inf. Process. Lett. 44(6): 303-306 (1992)
- [j4]Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan: Algebraic Methods for Interactive Proof Systems. J. ACM 39(4): 859-868 (1992)
- [c17]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
- [c16]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
- [c15]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: The Isomorphism Conjecture Holds Relative to an Oracle. FOCS 1992: 30-39
- 1991
- [j3]László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1: 3-40 (1991)
- [j2]László Babai, Lance Fortnow: Arithmetization: A New Method in Structural Complexity Theory. Computational Complexity 1: 41-66 (1991)
- [c14]
- [c13]Lance Fortnow, Nick Reingold: PP is Closed Under Truth-Table Reductions. Structure in Complexity Theory Conference 1991: 13-15
- [c12]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz: Gap-Definable Counting Classes. Structure in Complexity Theory Conference 1991: 30-42
- [c11]Joan Feigenbaum, Lance Fortnow: On the Random-Self-Reducibility of Complete Sets. Structure in Complexity Theory Conference 1991: 124-132
- [c10]Lance Fortnow, Carsten Lund: Interactive Proof Systems and Alternating Time-Space Complexity. STACS 1991: 263-274
- [c9]László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy: Checking Computations in Polylogarithmic Time. STOC 1991: 21-31
- 1990
- [c8]Lance Fortnow, John Rompel, Michael Sipser: Errata for On the Power of Multi-Prover Interactive Protocols. Structure in Complexity Theory Conference 1990: 318-319
- [c7]Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan: Algebraic Methods for Interactive Proof Systems. FOCS 1990: 2-10
- [c6]László Babai, Lance Fortnow, Carsten Lund: Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. FOCS 1990: 16-25
- [c5]László Babai, Lance Fortnow: A Characterization of \sharp P Arithmetic Straight Line Programs. FOCS 1990: 26-34
1980 – 1989
- 1989
- [c4]
- 1988
- [j1]Lance Fortnow, Michael Sipser: Are There Interactive Protocols for CO-NP Languages? Inf. Process. Lett. 28(5): 249-251 (1988)
- [c3]Lance Fortnow, John Rompel, Michael Sipser: On the power of multi-power interactive protocols. Structure in Complexity Theory Conference 1988: 156-161
- 1987
- [c2]Lance Fortnow: The complexity of perfect zero-knowledge. Structure in Complexity Theory Conference 1987
- [c1]
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-10-02 11:12 CEST by the dblp team