dblp.uni-trier.dewww.uni-trier.de

Lance Fortnow

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo
Home Page

2009
167EELance 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
164EELance Fortnow, Rakesh Vohra: The complexity of forecast testing: abstract. ACM Conference on Electronic Commerce 2008: 139
163EEYiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of combinatorial market makers. ACM Conference on Electronic Commerce 2008: 190-199
162EELance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142
161EEYiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of Combinatorial Market Makers CoRR abs/0802.1362: (2008)
160EELance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 (2008)
159EENikhil R. Devanur, Lance Fortnow: A Computational Theory of Awareness and Decision Making. Electronic Colloquium on Computational Complexity (ECCC) 15(046): (2008)
158EELance 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)
157EEHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
2007
156EEYiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Betting on permutations. ACM Conference on Electronic Commerce 2007: 326-335
155EEManindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
154EEManindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
153EEHarry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
152EELuis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. IEEE Conference on Computational Complexity 2007: 46-51
151EEYiling 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
150EELance Fortnow, Rahul Santhanam: Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004): (2007)
149EELance Fortnow, Rahul Santhanam: Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096): (2007)
148EEYiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Combinatorial betting. SIGecom Exchanges 7(1): 61-64 (2007)
2006
147EELance Fortnow, Adam R. Klivans: Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363
146EELance 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
145EELance Fortnow, Mitsunori Ogihara: Very Sparse Leaf Languages. MFCS 2006: 375-386
144EELance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
143EELance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space. STACS 2006: 469-476
142EERichard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)
141EEHarry 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)
140EELuis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Electronic Colloquium on Computational Complexity (ECCC) 13(125): (2006)
139EELance Fortnow, Rakesh Vohra: The Complexity of Forecast Testing. Electronic Colloquium on Computational Complexity (ECCC) 13(149): (2006)
138EELance Fortnow, Rahul Santhanam: Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157): (2006)
137EERichard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. SIAM J. Comput. 36(3): 595-608 (2006)
136EELuis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran: Computational depth: Concept and applications. Theor. Comput. Sci. 354(3): 391-404 (2006)
135EEEldar 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
133EEEldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties. IEEE Conference on Computational Complexity 2005: 135-140
132EELance Fortnow, Adam R. Klivans: NP with Small Advice. IEEE Conference on Computational Complexity 2005: 228-234
131EELance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. IEEE Conference on Computational Complexity 2005: 323-332
130EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity. STACS 2005: 412-421
129EELance Fortnow: Beyond NP: the work and legacy of Larry Stockmeyer. STOC 2005: 120-127
128EELance Fortnow, Rahul Santhanam, Luca Trevisan: Hierarchies for semantic classes. STOC 2005: 348-355
127EELance 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)
126EELance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space Electronic Colloquium on Computational Complexity (ECCC)(042): (2005)
125EELance 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)
124EELance Fortnow, Luis Antunes: Time-Bounded Universal Distributions Electronic Colloquium on Computational Complexity (ECCC)(144): (2005)
123EELance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas: Time-space lower bounds for satisfiability. J. ACM 52(6): 835-865 (2005)
122EELance Fortnow, Jack H. Lutz: Prediction and dimension. J. Comput. Syst. Sci. 70(4): 570-589 (2005)
121EEArtur 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)
120EEJoan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami: Computation in a distributed information market. Theor. Comput. Sci. 343(1-2): 114-132 (2005)
119EEHarry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. Theory Comput. Syst. 38(2): 211-227 (2005)
2004
118EEHarry Buhrman, Lance Fortnow, Thomas Thierauf: 04421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2004
117EELance Fortnow, Rahul Santhanam: Hierarchy Theorems for Probabilistic Polynomial Time. FOCS 2004: 316-324
116EELance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the complexity of succinct zero-sum games Electronic Colloquium on Computational Complexity (ECCC)(001): (2004)
115EERichard 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)
114EELance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error Electronic Colloquium on Computational Complexity (ECCC)(080): (2004)
113EEHarry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin: Increasing Kolmogorov Complexity Electronic Colloquium on Computational Complexity (ECCC)(081): (2004)
112EELance Fortnow, Rahul Santhanam, Luca Trevisan: Promise Hierarchies Electronic Colloquium on Computational Complexity (ECCC)(098): (2004)
111EELance Fortnow, Adam R. Klivans: NP with Small Advice Electronic Colloquium on Computational Complexity (ECCC)(103): (2004)
110EEEldar Fischer, Lance Fortnow: Tolerant Versus Intolerant Testing for Boolean Properties Electronic Colloquium on Computational Complexity (ECCC)(105): (2004)
109EELance Fortnow: Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. SIGACT News 35(2): 16-18 (2004)
2003
108EELance 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
107EEJoan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami: Computation in a distributed information market. ACM Conference on Electronic Commerce 2003: 156-165
106EELuis Antunes, Lance Fortnow, N. V. Vinodchandran: Using Depth to Capture Average-Case Complexity. FCT 2003: 303-310
105EELuis Antunes, Lance Fortnow: Sophistication Revisited. ICALP 2003: 267-277
104EERichard Beigel, Lance Fortnow: Are Cook and Karp Ever the Same? IEEE Conference on Computational Complexity 2003: 333-336
103EELance 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-
102EERichard Beigel, Lance Fortnow, Frank Stephan: Infinitely-Often Autoreducible Sets. ISAAC 2003: 98-107
101EEHarry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum property testing. SODA 2003: 480-488
100EEArtur 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
99EEHarry Buhrman, Lance Fortnow, Aduri Pavan: Some Results on Derandomization. STACS 2003: 212-222
98EEHarry 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)
96EERichard Beigel, Lance Fortnow, William I. Gasarch: A Nearly Tight Bound for Private Information Retrieval Protocols Electronic Colloquium on Computational Complexity (ECCC)(087): (2003)
95EEStephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li: An oracle builder's toolkit. Inf. Comput. 182(2): 95-136 (2003)
94EEStephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers: Inverting onto functions. Inf. Comput. 186(1): 90-103 (2003)
93EERodney 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
91EELance Fortnow, Jack H. Lutz: Prediction and Dimension. COLT 2002: 380-395
90EELance Fortnow: The History of Complexity. IEEE Conference on Computational Complexity 2002: 61
89EELance 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
87EELuis Antunes, Lance Fortnow, Dieter van Melkebeek: Computational Depth. IEEE Conference on Computational Complexity 2001: 266-273
86EELance Fortnow: Comparing Notions of Full Derandomization. IEEE Conference on Computational Complexity 2001: 28-34
85EERichard 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
83EEHarry 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)
81EEHarry Buhrman, Lance Fortnow, Sophie Laplante: Resource-Bounded Kolmogorov Complexity Revisited. SIAM J. Comput. 31(3): 887-905 (2001)
80EELance 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
78EELance Fortnow, Dieter van Melkebeek: Time-Space Tradeoffs for Nondeterministic Computation. IEEE Conference on Computational Complexity 2000: 2-13
77EEHarry 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)
75EELance Fortnow: One Complexity Theorist's View of Quantum Computing CoRR quant-ph/0003035: (2000)
74EELance Fortnow: One complexity theorist's view of quantum computing. Electr. Notes Theor. Comput. Sci. 31: (2000)
73EELance 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
70EELance Fortnow, Aduri Pavan, Alan L. Selman: Distributionally-Hard Languages. COCOON 1999: 184-193
69EEHarry Buhrman, Lance Fortnow: One-sided Versus Two-sided Error in Probabilistic Computation. STACS 1999: 100-109
68EELance 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
65EEHarry Buhrman, Lance Fortnow: Two Queries. IEEE Conference on Computational Complexity 1998: 13-
64EELance Fortnow, John D. Rogers: Complexity Limitations on Quantum Computation. IEEE Conference on Computational Complexity 1998: 202-209
63EERodney G. Downey, Lance Fortnow: Uniformly Hard Languages. IEEE Conference on Computational Complexity 1998: 228-
62EEHarry 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
60EERichard 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
58EELance 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)
55EELance 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
53EEHarry Buhrman, Lance Fortnow, Leen Torenvliet: Six Hypotheses in Search of a Theorem. IEEE Conference on Computational Complexity 1997: 2-12
52EELance 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
50EELance Fortnow, Michael Sipser: Retraction of Probabilistic Computation and Linear Time. STOC 1997: 750
1996
49EEStephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers: Inverting Onto Functions. IEEE Conference on Computational Complexity 1996: 213-222
48EEJoan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik: On Coherence, Random-self-reducibility, and Self-correction. IEEE Conference on Computational Complexity 1996: 59-67
47EELance 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)
42EELance 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
34EELance 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)
29EELance 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
21EEPeter 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)
16EECarsten 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

Coauthor Index

1Manindra Agrawal [154] [155] [165]
2Noga Alon [85]
3Luis Antunes [140]
4Luis Filipe Coelho Antunes (Luis Antunes) [87] [105] [106] [124] [136] [152]
5Mehmet Serkan Apaydin [85]
6László Babai [5] [7] [8] [9] [13] [18] [24]
7Tugkan Batu [79] [88]
8Richard Beigel [60] [85] [96] [102] [104] [115] [137] [142]
9Harry Buhrman [41] [51] [53] [54] [60] [62] [65] [67] [69] [71] [77] [81] [83] [98] [99] [101] [113] [115] [118] [119] [130] [134] [141] [153] [154] [155] [157] [165]
10Richard Chang [98]
11Yiling Chen [148] [151] [156] [161] [163]
12Peter Cholak [21]
13Artur Czumaj [100] [121]
14Nikhil R. Devanur [159]
15Rodney G. Downey (Rod Downey) [21] [63] [93]
16Funda Ergün [100] [121]
17Joan Feigenbaum [12] [19] [23] [30] [48] [57] [107] [120]
18Peter A. Fejer [115]
19Stephen A. Fenner [10] [20] [25] [26] [28] [38] [43] [45] [49] [54] [77] [83] [94] [95]
20Eldar Fischer [88] [110] [133] [135]
21Rusins Freivalds [40] [55]
22William I. Gasarch [21] [32] [40] [55] [96] [142]
23Judy Goldsmith [47] [56]
24Rica Gonen [151]
25Piotr Grabowski [115]
26Robin D. Hanson [151]
27John M. Hitchcock [125] [146]
28Steven Homer [97]
29Russell Impagliazzo [116] [131] [160]
30Sanjay Jain [32]
31Valentine Kabanets [116] [131] [160]
32Howard J. Karloff [6] [16]
33Simon Kasif [85]
34Joe Kilian [108] [127]
35Peter G. Kimmel [59]
36Efim B. Kinber [21] [32]
37Adam R. Klivans (Adam Klivans) [111] [126] [132] [143] [147] [167]
38Michal Koucký [141] [153]
39Ravi Kumar (S. Ravi Kumar) [88]
40Martin Kummer [21] [32] [39] [40] [42] [55]
41Stuart A. Kurtz [10] [20] [21] [25] [28] [32] [40] [43] [55] [95]
42Nicolas S. Lambert [161] [163]
43Sophie Laplante [37] [48] [57] [61] [81]
44Troy Lee [114] [144]
45Leonid A. Levin [13]
46Matthew A. Levy [56]
47Lide Li [25] [26] [45] [95]
48Richard J. Lipton [123]
49Luc Longpré [115]
50Carsten Lund [6] [7] [9] [14] [16] [18] [19] [22] [30]
51Jack H. Lutz [91] [122]
52Avner Magen [100] [121]
53Stephen R. Mahaney [47] [56]
54Dieter van Melkebeek [71] [73] [77] [78] [87] [123] [136]
55Andrej Muchnik (Andrei A. Muchnik) [115]
56Ashish V. Naik [48] [49] [57] [94]
57Ilan Newman [100] [101] [113] [121] [130] [157]
58Evdokia Nikolova [148] [156]
59Noam Nisan [6] [16] [24]
60Mitsunori Ogihara (Mitsunori Ogiwara) [145]
61Aduri Pavan [70] [80] [99] [103] [119] [125] [146] [158]
62David M. Pennock (David Pennock) [107] [108] [120] [127] [148] [151] [156] [161] [163]
63Alexandre Pinto [140] [152]
64Mark Pleszkovich [32]
65Daniel M. Reeves [151]
66Nick Reingold [11] [46]
67John Riedl [166]
68John D. Rogers [35] [49] [58] [64] [66] [89] [94] [141] [153]
69Hein Röhrig [101] [157]
70John Rompel [4] [27]
71Ronitt Rubinfeld [79] [88] [100] [121]
72Rahul Sami [107] [120]
73Tuomas Sandholm [166]
74Rahul Santhanam [112] [117] [128] [138] [149] [150] [162]
75Alan L. Selman [70] [80]
76Samik Sengupta [103] [158]
77Michael Sipser [2] [3] [4] [27] [50]
78Theodore A. Slaman [21] [32]
79Carl H. Smith [40] [55]
80Warren D. Smith [79]
81Christian Sohler [100] [121]
82Robert Solovay [32]
83Andre Souto [140] [152]
84Daniel A. Spielman [19] [30]
85Frank Stephan [32] [40] [55] [102] [115] [137]
86Mario Szegedy [13] [15] [17]
87Thomas Thierauf [62] [118] [134] [154] [155] [165]
88Leen Torenvliet [41] [53] [71] [83] [115]
89Luca Trevisan [112] [128]
90Christopher Umans [116] [131] [160]
91Nikolai K. Vereshchagin [113] [114] [130] [141] [144] [153]
92Anastasios Viglas [123]
93N. V. Vinodchandran (N. Variyam Vinodchandran) [106] [125] [136] [146]
94Rakesh V. Vohra (Rakesh Vohra) [139] [164]
95Fengming Wang [125] [146]
96Michael P. Wellman [108] [127]
97Duke Whang [34]
98Patrick White [79] [88]
99Avi Wigderson [24]
100Jennifer Wortman [161] [163]
101Tomoyuki Yamakami [33] [44]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)