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