 | 2009 |
|---|
| 184 |       | John Chuang,
Lance Fortnow,
Pearl Pu:
Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009
ACM 2009 |
| 183 |  | Harry Buhrman,
Lance Fortnow,
Rahul Santhanam:
Unconditional Lower Bounds against Advice.
ICALP (1) 2009: 195-209 |
| 182 | | Lance Fortnow,
Rahul Santhanam,
Ryan Williams:
Fixed-Polynomial Size Circuit Bounds.
IEEE Conference on Computational Complexity 2009: 19-26 |
| 181 | | Luis Filipe Coelho Antunes,
Lance Fortnow:
Worst-Case Running Times for Average-Case Algorithms.
IEEE Conference on Computational Complexity 2009: 298-303 |
| 180 | | Lance Fortnow:
Program equilibria and discounted computation time.
TARK 2009: 128-133 |
| 179 | | Nikhil R. Devanur,
Lance Fortnow:
A computational theory of awareness and decision making.
TARK 2009: 99-107 |
| 178 | | Lance Fortnow,
Joshua A. Grochow:
Complexity Classes of Equivalence Problems Revisited
CoRR abs/0907.4775: (2009) |
| 177 | | Lance Fortnow,
Rahul Santhanam:
Bounding Rationality by Discounting Time
CoRR abs/0911.3162: (2009) |
| 176 | | Harry Buhrman,
Lance Fortnow,
Michal Koucký,
Bruno Loff:
Derandomizing from Random Strings
CoRR abs/0912.3162: (2009) |
| 175 | | Lance Fortnow:
Viewpoint - Time for computer science to grow up.
Commun. ACM 52(8): 33-35 (2009) |
| 174 | | Lance Fortnow:
The status of the P versus NP problem.
Commun. ACM 52(9): 78-86 (2009) |
| 173 | | Lance Fortnow,
Adam R. Klivans:
Efficient learning algorithms yield circuit lower bounds.
J. Comput. Syst. Sci. 75(1): 27-36 (2009) |
| 172 | | Lance Fortnow:
Editor's Foreword.
TOCT 1(1): (2009) |
| 171 | | Luis Filipe Coelho Antunes,
Lance Fortnow:
Sophistication Revisited.
Theory Comput. Syst. 45(1): 150-161 (2009) |
| 2008 |
|---|
| 170 | | Lance Fortnow,
John Riedl,
Tuomas Sandholm:
Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008
ACM 2008 |
| 169 | | Manindra Agrawal,
Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007
Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2008 |
| 168 | | Lance Fortnow,
Rakesh Vohra:
The complexity of forecast testing: abstract.
ACM Conference on Electronic Commerce 2008: 139 |
| 167 | | 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 |
| 166 | | Lance Fortnow,
Rahul Santhanam:
Infeasibility of instance compression and succinct PCPs for NP.
STOC 2008: 133-142 |
| 165 | | Yiling Chen,
Lance Fortnow,
Nicolas S. Lambert,
David M. Pennock,
Jennifer Wortman:
Complexity of Combinatorial Market Makers
CoRR abs/0802.1362: (2008) |
| 164 | | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the Complexity of Succinct Zero-Sum Games.
Computational Complexity 17(3): 353-376 (2008) |
| 163 | | Nikhil R. Devanur,
Lance Fortnow:
A Computational Theory of Awareness and Decision Making.
Electronic Colloquium on Computational Complexity (ECCC) 15(046): (2008) |
| 162 | | 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) |
| 161 | | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Hein Röhrig:
Quantum Property Testing.
SIAM J. Comput. 37(5): 1387-1400 (2008) |
| 160 | | Lance Fortnow,
Rakesh V. Vohra:
The complexity of forecast testing.
SIGecom Exchanges 7(3): (2008) |
| 2007 |
|---|
| 159 | | Yiling Chen,
Lance Fortnow,
Evdokia Nikolova,
David M. Pennock:
Betting on permutations.
ACM Conference on Electronic Commerce 2007: 326-335 |
| 158 | | Manindra Agrawal,
Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.
Algebraic Methods in Computational Complexity 2007 |
| 157 | | Manindra Agrawal,
Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
07411 Executive Summary -- Algebraic Methods in Computational Complexity.
Algebraic Methods in Computational Complexity 2007 |
| 156 | | Harry Buhrman,
Lance Fortnow,
Michal Koucký,
John D. Rogers,
Nikolai K. Vereshchagin:
Inverting Onto Functions and Polynomial Hierarchy.
CSR 2007: 92-103 |
| 155 | | Luis Antunes,
Lance Fortnow,
Alexandre Pinto,
Andre Souto:
Low-Depth Witnesses are Easy to Find.
IEEE Conference on Computational Complexity 2007: 46-51 |
| 154 | | 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 |
| 153 | | Lance Fortnow,
Rahul Santhanam:
Time Hierarchies: A Survey.
Electronic Colloquium on Computational Complexity (ECCC) 14(004): (2007) |
| 152 | | Lance Fortnow,
Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP.
Electronic Colloquium on Computational Complexity (ECCC) 14(096): (2007) |
| 151 | | Yiling Chen,
Lance Fortnow,
Evdokia Nikolova,
David M. Pennock:
Combinatorial betting.
SIGecom Exchanges 7(1): 61-64 (2007) |
| 2006 |
|---|
| 150 | | Lance Fortnow,
Adam R. Klivans:
Efficient Learning Algorithms Yield Circuit Lower Bounds.
COLT 2006: 350-363 |
| 149 | | 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 |
| 148 | | Lance Fortnow,
Mitsunori Ogihara:
Very Sparse Leaf Languages.
MFCS 2006: 375-386 |
| 147 | | Lance Fortnow,
Troy Lee,
Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error.
STACS 2006: 137-148 |
| 146 | | Lance Fortnow,
Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space.
STACS 2006: 469-476 |
| 145 | | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A tight lower bound for restricted pir protocols.
Computational Complexity 15(1): 82-91 (2006) |
| 144 | | 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) |
| 143 | | Luis Antunes,
Lance Fortnow,
Alexandre Pinto,
Andre Souto:
Low-Depth Witnesses are Easy to Find.
Electronic Colloquium on Computational Complexity (ECCC) 13(125): (2006) |
| 142 | | Lance Fortnow,
Rakesh Vohra:
The Complexity of Forecast Testing.
Electronic Colloquium on Computational Complexity (ECCC) 13(149): (2006) |
| 141 | | Lance Fortnow,
Rahul Santhanam:
Fixed-Polynomial Size Circuit Bounds.
Electronic Colloquium on Computational Complexity (ECCC) 13(157): (2006) |
| 140 | | Richard Beigel,
Lance Fortnow,
Frank Stephan:
Infinitely-Often Autoreducible Sets.
SIAM J. Comput. 36(3): 595-608 (2006) |
| 139 | | Luis Antunes,
Lance Fortnow,
Dieter van Melkebeek,
N. V. Vinodchandran:
Computational depth: Concept and applications.
Theor. Comput. Sci. 354(3): 391-404 (2006) |
| 138 | | Eldar Fischer,
Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties.
Theory of Computing 2(1): 173-183 (2006) |
| 2005 |
|---|
| 137 | | Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
Algebraic Methods in Computational Complexity, 10.-15. October 2004
IBFI, Schloss Dagstuhl, Germany 2005 |
| 136 | | Eldar Fischer,
Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties.
IEEE Conference on Computational Complexity 2005: 135-140 |
| 135 | | Lance Fortnow,
Adam R. Klivans:
NP with Small Advice.
IEEE Conference on Computational Complexity 2005: 228-234 |
| 134 | | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the Complexity of Succinct Zero-Sum Games.
IEEE Conference on Computational Complexity 2005: 323-332 |
| 133 | | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity.
STACS 2005: 412-421 |
| 132 | | Lance Fortnow:
Beyond NP: the work and legacy of Larry Stockmeyer.
STOC 2005: 120-127 |
| 131 | | Lance Fortnow,
Rahul Santhanam,
Luca Trevisan:
Hierarchies for semantic classes.
STOC 2005: 348-355 |
| 130 | | 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) |
| 129 | | Lance Fortnow,
Adam R. Klivans:
Linear Advice for Randomized Logarithmic Space
Electronic Colloquium on Computational Complexity (ECCC)(042): (2005) |
| 128 | | 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) |
| 127 | | Lance Fortnow,
Luis Antunes:
Time-Bounded Universal Distributions
Electronic Colloquium on Computational Complexity (ECCC)(144): (2005) |
| 126 | | Lance Fortnow,
Richard J. Lipton,
Dieter van Melkebeek,
Anastasios Viglas:
Time-space lower bounds for satisfiability.
J. ACM 52(6): 835-865 (2005) |
| 125 | | Lance Fortnow,
Jack H. Lutz:
Prediction and dimension.
J. Comput. Syst. Sci. 70(4): 570-589 (2005) |
| 124 | | 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) |
| 123 | | Joan Feigenbaum,
Lance Fortnow,
David M. Pennock,
Rahul Sami:
Computation in a distributed information market.
Theor. Comput. Sci. 343(1-2): 114-132 (2005) |
| 122 | | Harry Buhrman,
Lance Fortnow,
Aduri Pavan:
Some Results on Derandomization.
Theory Comput. Syst. 38(2): 211-227 (2005) |
| 2004 |
|---|
| 121 | | Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
04421 Abstracts Collection - Algebraic Methods in Computational Complexity.
Algebraic Methods in Computational Complexity 2004 |
| 120 | | Lance Fortnow,
Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time.
FOCS 2004: 316-324 |
| 119 | | Lance Fortnow,
Russell Impagliazzo,
Valentine Kabanets,
Christopher Umans:
On the complexity of succinct zero-sum games
Electronic Colloquium on Computational Complexity (ECCC)(001): (2004) |
| 118 | | 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) |
| 117 | | Lance Fortnow,
Troy Lee,
Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error
Electronic Colloquium on Computational Complexity (ECCC)(080): (2004) |
| 116 | | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity
Electronic Colloquium on Computational Complexity (ECCC)(081): (2004) |
| 115 | | Lance Fortnow,
Rahul Santhanam,
Luca Trevisan:
Promise Hierarchies
Electronic Colloquium on Computational Complexity (ECCC)(098): (2004) |
| 114 | | Lance Fortnow,
Adam R. Klivans:
NP with Small Advice
Electronic Colloquium on Computational Complexity (ECCC)(103): (2004) |
| 113 | | Eldar Fischer,
Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties
Electronic Colloquium on Computational Complexity (ECCC)(105): (2004) |
| 112 | | Lance Fortnow:
Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer.
SIGACT News 35(2): 16-18 (2004) |
| 2003 |
|---|
| 111 | | 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 |
| 110 | | Joan Feigenbaum,
Lance Fortnow,
David M. Pennock,
Rahul Sami:
Computation in a distributed information market.
ACM Conference on Electronic Commerce 2003: 156-165 |
| 109 | | Luis Antunes,
Lance Fortnow,
N. V. Vinodchandran:
Using Depth to Capture Average-Case Complexity.
FCT 2003: 303-310 |
| 108 | | Luis Antunes,
Lance Fortnow:
Sophistication Revisited.
ICALP 2003: 267-277 |
| 107 | | Richard Beigel,
Lance Fortnow:
Are Cook and Karp Ever the Same?
IEEE Conference on Computational Complexity 2003: 333-336 |
| 106 | | 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- |
| 105 | | Richard Beigel,
Lance Fortnow,
Frank Stephan:
Infinitely-Often Autoreducible Sets.
ISAAC 2003: 98-107 |
| 104 | | Harry Buhrman,
Lance Fortnow,
Ilan Newman,
Hein Röhrig:
Quantum property testing.
SODA 2003: 480-488 |
| 103 | | 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 |
| 102 | | Harry Buhrman,
Lance Fortnow,
Aduri Pavan:
Some Results on Derandomization.
STACS 2003: 212-222 |
| 101 | | Harry Buhrman,
Richard Chang,
Lance Fortnow:
One Bit of Advice.
STACS 2003: 547-558 |
| 100 | | Lance Fortnow,
Steven Homer:
A Short History of Computational Complexity.
Bulletin of the EATCS 80: 95-133 (2003) |
| 99 | | Richard Beigel,
Lance Fortnow,
William I. Gasarch:
A Nearly Tight Bound for Private Information Retrieval Protocols
Electronic Colloquium on Computational Complexity (ECCC)(087): (2003) |
| 98 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz,
Lide Li:
An oracle builder's toolkit.
Inf. Comput. 182(2): 95-136 (2003) |
| 97 | | Stephen A. Fenner,
Lance Fortnow,
Ashish V. Naik,
John D. Rogers:
Inverting onto functions.
Inf. Comput. 186(1): 90-103 (2003) |
| 96 | | Rodney G. Downey,
Lance Fortnow:
Uniformly hard languages.
Theor. Comput. Sci. 2(298): 303-315 (2003) |
| 95 | | Lance Fortnow:
One complexity theorist's view of quantum computing.
Theor. Comput. Sci. 292(3): 597-610 (2003) |
| 2002 |
|---|
| 94 | | Lance Fortnow,
Jack H. Lutz:
Prediction and Dimension.
COLT 2002: 380-395 |
| 93 | | Lance Fortnow:
The History of Complexity.
IEEE Conference on Computational Complexity 2002: 61 |
| 92 | | Lance Fortnow,
John D. Rogers:
Separability and one-way functions.
Computational Complexity 11(3-4): 137-157 (2002) |
| 2001 |
|---|
| 91 | | Tugkan Batu,
Lance Fortnow,
Eldar Fischer,
Ravi Kumar,
Ronitt Rubinfeld,
Patrick White:
Testing Random Variables for Independence and Identity.
FOCS 2001: 442-451 |
| 90 | | Luis Antunes,
Lance Fortnow,
Dieter van Melkebeek:
Computational Depth.
IEEE Conference on Computational Complexity 2001: 266-273 |
| 89 | | Lance Fortnow:
Comparing Notions of Full Derandomization.
IEEE Conference on Computational Complexity 2001: 28-34 |
| 88 | | 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 |
| 87 | | Lance Fortnow:
Diagonalization.
Current Trends in Theoretical Computer Science 2001: 102-114 |
| 86 | | Harry Buhrman,
Stephen A. Fenner,
Lance Fortnow,
Leen Torenvliet:
Two oracles that force a big crunch.
Computational Complexity 10(2): 93-116 (2001) |
| 85 | | Lance Fortnow:
Guest Editor's Foreword.
J. Comput. Syst. Sci. 62(2): 215 (2001) |
| 84 | | Harry Buhrman,
Lance Fortnow,
Sophie Laplante:
Resource-Bounded Kolmogorov Complexity Revisited.
SIAM J. Comput. 31(3): 887-905 (2001) |
| 83 | | Lance Fortnow,
Aduri Pavan,
Alan L. Selman:
Distributionally Hard Languages.
Theory Comput. Syst. 34(3): 245-261 (2001) |
| 2000 |
|---|
| 82 | | Tugkan Batu,
Lance Fortnow,
Ronitt Rubinfeld,
Warren D. Smith,
Patrick White:
Testing that distributions are close.
FOCS 2000: 259-269 |
| 81 | | Lance Fortnow,
Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation.
IEEE Conference on Computational Complexity 2000: 2-13 |
| 80 | | Harry Buhrman,
Stephen A. Fenner,
Lance Fortnow,
Dieter van Melkebeek:
Optimal Proof Systems and Sparse Sets.
STACS 2000: 407-418 |
| 79 | | Lance Fortnow:
Diagonalization.
Bulletin of the EATCS 71: 102-113 (2000) |
| 78 | | Lance Fortnow:
One Complexity Theorist's View of Quantum Computing
CoRR quant-ph/0003035: (2000) |
| 77 | | Lance Fortnow:
One complexity theorist's view of quantum computing.
Electr. Notes Theor. Comput. Sci. 31: (2000) |
| 76 | | Lance Fortnow,
Dieter van Melkebeek:
Time-Space Tradeoffs for Nondeterministic Computation
Electronic Colloquium on Computational Complexity (ECCC) 7(28): (2000) |
| 75 | | Lance Fortnow:
Time-Space Tradeoffs for Satisfiability.
J. Comput. Syst. Sci. 60(2): 337-353 (2000) |
| 74 | | Harry Buhrman,
Lance Fortnow,
Dieter van Melkebeek,
Leen Torenvliet:
Separating Complexity Classes Using Autoreducibility.
SIAM J. Comput. 29(5): 1497-1520 (2000) |
| 1999 |
|---|
| 73 | | Lance Fortnow,
Aduri Pavan,
Alan L. Selman:
Distributionally-Hard Languages.
COCOON 1999: 184-193 |
| 72 | | Harry Buhrman,
Lance Fortnow:
One-sided Versus Two-sided Error in Probabilistic Computation.
STACS 1999: 100-109 |
| 71 | | Lance Fortnow:
Relativized Worlds with an Infinite Hierarchy.
Inf. Process. Lett. 69(6): 309-313 (1999) |
| 70 | | Harry Buhrman,
Lance Fortnow:
Two Queries.
J. Comput. Syst. Sci. 59(2): 182-194 (1999) |
| 69 | | Lance Fortnow,
John D. Rogers:
Complexity Limitations on Quantum Computation.
J. Comput. Syst. Sci. 59(2): 240-252 (1999) |
| 68 | | 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 |
|---|
| 67 | | Harry Buhrman,
Lance Fortnow:
Two Queries.
IEEE Conference on Computational Complexity 1998: 13- |
| 66 | | Lance Fortnow,
John D. Rogers:
Complexity Limitations on Quantum Computation.
IEEE Conference on Computational Complexity 1998: 202-209 |
| 65 | | Rodney G. Downey,
Lance Fortnow:
Uniformly Hard Languages.
IEEE Conference on Computational Complexity 1998: 228- |
| 64 | | Harry Buhrman,
Lance Fortnow,
Thomas Thierauf:
Nonrelativizing Separations.
IEEE Conference on Computational Complexity 1998: 8-12 |
| 63 | | Lance Fortnow,
Sophie Laplante:
Nearly Optimal Language Compression Using Extractors.
STACS 1998: 84-93 |
| 62 | | Richard Beigel,
Harry Buhrman,
Lance Fortnow:
NP Might Not Be As Easy As Detecting Unique Solutions.
STOC 1998: 203-208 |
| 61 | | Lance Fortnow,
Peter G. Kimmel:
Beating a Finite Automaton in the Big Match.
TARK 1998: 225-234 |
| 60 | | Lance Fortnow,
John D. Rogers:
Complexity limitations on quantum computation
CoRR cs.CC/9811023: (1998) |
| 59 | | Joan Feigenbaum,
Lance Fortnow,
Sophie Laplante,
Ashish V. Naik:
On Coherence, Random-Self-Reducibility, and Self-Correction.
Computational Complexity 7(2): 174-191 (1998) |
| 58 | | Lance Fortnow,
Judy Goldsmith,
Matthew A. Levy,
Stephen R. Mahaney:
L-Printable Sets.
SIAM J. Comput. 28(1): 137-151 (1998) |
| 57 | | 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) |
| 1997 |
|---|
| 56 | | Harry Buhrman,
Stephen A. Fenner,
Lance Fortnow:
Results on Resource-Bounded Measure.
ICALP 1997: 188-194 |
| 55 | | Harry Buhrman,
Lance Fortnow,
Leen Torenvliet:
Six Hypotheses in Search of a Theorem.
IEEE Conference on Computational Complexity 1997: 2-12 |
| 54 | | Lance Fortnow:
Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability.
IEEE Conference on Computational Complexity 1997: 52-60 |
| 53 | | Harry Buhrman,
Lance Fortnow:
Resource-Bounded Kolmogorov Complexity Revisited.
STACS 1997: 105-116 |
| 52 | | Lance Fortnow,
Michael Sipser:
Retraction of Probabilistic Computation and Linear Time.
STOC 1997: 750 |
| 1996 |
|---|
| 51 | | Stephen A. Fenner,
Lance Fortnow,
Ashish V. Naik,
John D. Rogers:
Inverting Onto Functions.
IEEE Conference on Computational Complexity 1996: 213-222 |
| 50 | | 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 |
| 49 | | Lance Fortnow,
Judy Goldsmith,
Stephen R. Mahaney:
L-Printable Sets.
IEEE Conference on Computational Complexity 1996: 97-106 |
| 48 | | Lance Fortnow,
Nick Reingold:
PP is Closed Under Truth-Table Reductions.
Inf. Comput. 124(1): 1-6 (1996) |
| 47 | | Stephen A. Fenner,
Lance Fortnow,
Lide Li:
Gap-Definability as a Closure Property.
Inf. Comput. 130(1): 1-17 (1996) |
| 46 | | Lance Fortnow,
Tomoyuki Yamakami:
Generic Separations.
J. Comput. Syst. Sci. 52(1): 191-197 (1996) |
| 45 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle.
SIAM J. Comput. 25(1): 193-206 (1996) |
| 44 | | Stephen A. Fenner,
Lance Fortnow,
William I. Gasarch:
Complexity Theory Newsflash.
SIGACT News 27(3): 126 (1996) |
| 43 | | Lance Fortnow,
Martin Kummer:
On Resource-Bounded Instance Complexity.
Theor. Comput. Sci. 161(1&2): 123-140 (1996) |
| 1995 |
|---|
| 42 | | Harry Buhrman,
Lance Fortnow,
Leen Torenvliet:
Using Autoreducibility to Separate Complexity Classes.
FOCS 1995: 520-527 |
| 41 | | 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 |
| 40 | | Lance Fortnow,
Martin Kummer:
Resource-Bounded Instance Complexity (Extended Abstract).
STACS 1995: 597-608 |
| 39 | | Stephen A. Fenner,
Lance Fortnow:
Beyond P^(NP) - NEXP.
STACS 1995: 619-627 |
| 38 | | Lance Fortnow,
Sophie Laplante:
Circuit Lower Bounds à la Kolmogorov.
Inf. Comput. 123(1): 121-126 (1995) |
| 1994 |
|---|
| 37 | | Lance Fortnow:
My Favorite Ten Complexity Theorems of the Past Decade.
FSTTCS 1994: 256-275 |
| 36 | | Lance Fortnow,
John D. Rogers:
Separability and One-Way Functions.
ISAAC 1994: 396-404 |
| 35 | | Lance Fortnow,
Duke Whang:
Optimality and domination in repeated games with bounded players.
STOC 1994: 741-749 |
| 34 | | Lance Fortnow,
Tomoyuki Yamakami:
Generic Separations.
Structure in Complexity Theory Conference 1994: 139-145 |
| 33 | | 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) |
| 32 | | Lance Fortnow:
The Role of Relativization in Complexity Theory.
Bulletin of the EATCS 52: 229-243 (1994) |
| 31 | | 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) |
| 30 | | Lance Fortnow:
My Favorite Ten Complexity Theorems of the Past Decade
Electronic Colloquium on Computational Complexity (ECCC) 1(21): (1994) |
| 29 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz:
Gap-Definable Counting Classes.
J. Comput. Syst. Sci. 48(1): 116-148 (1994) |
| 28 | | 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) |
| 27 | | Lance Fortnow,
John Rompel,
Michael Sipser:
On the Power of Multi-Prover Interactive Protocols.
Theor. Comput. Sci. 134(2): 545-557 (1994) |
| 1993 |
|---|
| 26 | | Stephen A. Fenner,
Lance Fortnow,
Lide Li:
Gap-Definability as a Closure Property.
STACS 1993: 484-493 |
| 25 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz,
Lide Li:
An Oarcle Builder's Toolkit.
Structure in Complexity Theory Conference 1993: 120-131 |
| 24 | | 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) |
| 23 | | Joan Feigenbaum,
Lance Fortnow:
Random-Self-Reducibility of Complete Sets.
SIAM J. Comput. 22(5): 994-1005 (1993) |
| 22 | | Lance Fortnow,
Carsten Lund:
Interactive Proof Systems and Alternating Time-Space Complexity.
Theor. Comput. Sci. 113(1): 55-73 (1993) |
| 1992 |
|---|
| 21 | | 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 |
| 20 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz:
The Isomorphism Conjecture Holds Relative to an Oracle
FOCS 1992: 30-39 |
| 19 | | 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 |
| 18 | | László Babai,
Lance Fortnow,
Carsten Lund:
Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity 2: 374 (1992) |
| 17 | | Lance Fortnow,
Mario Szegedy:
On the Power of Two-Local Random Reductions.
Inf. Process. Lett. 44(6): 303-306 (1992) |
| 16 | | Carsten Lund,
Lance Fortnow,
Howard J. Karloff,
Noam Nisan:
Algebraic Methods for Interactive Proof Systems.
J. ACM 39(4): 859-868 (1992) |
| 1991 |
|---|
| 15 | | Lance Fortnow,
Mario Szegedy:
On the Power of Two-Local Random Reductions.
ASIACRYPT 1991: 346-351 |
| 14 | | Lance Fortnow,
Carsten Lund:
Interactive Proof Systems and Alternating Time-Space Complexity.
STACS 1991: 263-274 |
| 13 | | László Babai,
Lance Fortnow,
Leonid A. Levin,
Mario Szegedy:
Checking Computations in Polylogarithmic Time
STOC 1991: 21-31 |
| 12 | | Joan Feigenbaum,
Lance Fortnow:
On the Random-Self-Reducibility of Complete Sets.
Structure in Complexity Theory Conference 1991: 124-132 |
| 11 | | Lance Fortnow,
Nick Reingold:
PP is Closed Under Truth-Table Reductions.
Structure in Complexity Theory Conference 1991: 13-15 |
| 10 | | Stephen A. Fenner,
Lance Fortnow,
Stuart A. Kurtz:
Gap-Definable Counting Classes.
Structure in Complexity Theory Conference 1991: 30-42 |
| 9 | | László Babai,
Lance Fortnow,
Carsten Lund:
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity 1: 3-40 (1991) |
| 8 | | László Babai,
Lance Fortnow:
Arithmetization: A New Method in Structural Complexity Theory.
Computational Complexity 1: 41-66 (1991) |
| 1990 |
|---|
| 7 | | László Babai,
Lance Fortnow,
Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
FOCS 1990: 16-25 |
| 6 | | Carsten Lund,
Lance Fortnow,
Howard J. Karloff,
Noam Nisan:
Algebraic Methods for Interactive Proof Systems
FOCS 1990: 2-10 |
| 5 | | László Babai,
Lance Fortnow:
A Characterization of \sharp P Arithmetic Straight Line Programs
FOCS 1990: 26-34 |
| 4 | | Lance Fortnow,
John Rompel,
Michael Sipser:
Errata for On the Power of Multi-Prover Interactive Protocols.
Structure in Complexity Theory Conference 1990: 318-319 |
| 1989 |
|---|
| 3 | | Lance Fortnow,
Michael Sipser:
Probabilistic Computation and Linear Time
STOC 1989: 148-156 |
| 1988 |
|---|
| 2 | | Lance Fortnow,
Michael Sipser:
Are There Interactive Protocols for CO-NP Languages?
Inf. Process. Lett. 28(5): 249-251 (1988) |
| 1987 |
|---|
| 1 | | Lance Fortnow:
The Complexity of Perfect Zero-Knowledge (Extended Abstract)
STOC 1987: 204-209 |
