Lance Fortnow

	2012
202		Lance Fortnow, Rahul Sami: Multi-outcome and Multidimensional Market Scoring Rules CoRR abs/1202.1712: (2012)
201		Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. Theory Comput. Syst. 51(2): 229-247 (2012)
	2011
200		Lance Fortnow, Salil P. Vadhan: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 ACM 2011
199		Michele Budinich, Lance Fortnow: Repeated matching pennies with limited randomness. ACM Conference on Electronic Commerce 2011: 111-118
198		Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations. ICALP (1) 2011: 569-580
197		Michele Budinich, Lance Fortnow: Repeated Matching Pennies with Limited Randomness CoRR abs/1102.1096: (2011)
196		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)
195		Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1): 91-106 (2011)
	2010
194		Lance Fortnow, Rahul Santhanam: Bounding Rationality by Discounting Time. ICS 2010: 143-155
193		Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings. IEEE Conference on Computational Complexity 2010: 58-63
192		Lance Fortnow, Jack H. Lutz, Elvira Mayordomo: Inseparability and Strong Hypotheses for Disjoint NP Pairs. STACS 2010: 395-404
191		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)
190		Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White: Testing Closeness of Discrete Distributions CoRR abs/1009.5397: (2010)
189		Lance Fortnow, Rahul Santhanam: Robust Simulations and Significant Separations CoRR abs/1012.2034: (2010)
188		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)
	2009
187		John Chuang, Lance Fortnow, Pearl Pu: Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009 ACM 2009
186		Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. ICALP (1) 2009: 195-209
185		Lance Fortnow, Rahul Santhanam, Ryan Williams: Fixed-Polynomial Size Circuit Bounds. IEEE Conference on Computational Complexity 2009: 19-26
184		Luis Filipe Coelho Antunes, Lance Fortnow: Worst-Case Running Times for Average-Case Algorithms. IEEE Conference on Computational Complexity 2009: 298-303
183		Lance Fortnow: Program equilibria and discounted computation time. TARK 2009: 128-133
182		Nikhil R. Devanur, Lance Fortnow: A computational theory of awareness and decision making. TARK 2009: 99-107
181		Lance Fortnow, Joshua A. Grochow: Complexity Classes of Equivalence Problems Revisited CoRR abs/0907.4775: (2009)
180		Lance Fortnow, Rahul Santhanam: Bounding Rationality by Discounting Time CoRR abs/0911.3162: (2009)
179		Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff: Derandomizing from Random Strings CoRR abs/0912.3162: (2009)
178		Lance Fortnow: Viewpoint - Time for computer science to grow up. Commun. ACM 52(8): 33-35 (2009)
177		Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009)
176		Harry Buhrman, Lance Fortnow, Rahul Santhanam: Unconditional Lower Bounds against Advice. Electronic Colloquium on Computational Complexity (ECCC) 16: 64 (2009)
175		Lance Fortnow, Adam R. Klivans: Efficient learning algorithms yield circuit lower bounds. J. Comput. Syst. Sci. 75(1): 27-36 (2009)
174		Lance Fortnow: Editor's Foreword. TOCT 1(1): (2009)
173		Luis Filipe Coelho Antunes, Lance Fortnow: Sophistication Revisited. Theory Comput. Syst. 45(1): 150-161 (2009)
172		Lance Fortnow: A Simple Proof of Toda's Theorem. Theory of Computing 5(1): 135-140 (2009)
	2008
171		Lance Fortnow, John Riedl, Tuomas Sandholm: Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008 ACM 2008
170		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
169		Lance Fortnow, Rakesh Vohra: The complexity of forecast testing: abstract. ACM Conference on Electronic Commerce 2008: 139
168		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
167		Lance Fortnow, Rahul Santhanam: Infeasibility of instance compression and succinct PCPs for NP. STOC 2008: 133-142
166		Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman: Complexity of Combinatorial Market Makers CoRR abs/0802.1362: (2008)
165		Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3): 353-376 (2008)
164		Nikhil R. Devanur, Lance Fortnow: A Computational Theory of Awareness and Decision Making. Electronic Colloquium on Computational Complexity (ECCC) 15(046): (2008)
163		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)
162		Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig: Quantum Property Testing. SIAM J. Comput. 37(5): 1387-1400 (2008)
161		Lance Fortnow, Rakesh V. Vohra: The complexity of forecast testing. SIGecom Exchanges 7(3): (2008)
	2007
160		Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Betting on permutations. ACM Conference on Electronic Commerce 2007: 326-335
159		Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Abstracts Collection -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
158		Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf: 07411 Executive Summary -- Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2007
157		Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin: Inverting Onto Functions and Polynomial Hierarchy. CSR 2007: 92-103
156		Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. IEEE Conference on Computational Complexity 2007: 46-51
155		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
154		Lance Fortnow, Rahul Santhanam: Time Hierarchies: A Survey. Electronic Colloquium on Computational Complexity (ECCC) 14(004): (2007)
153		Lance Fortnow, Rahul Santhanam: Infeasibility of Instance Compression and Succinct PCPs for NP. Electronic Colloquium on Computational Complexity (ECCC) 14(096): (2007)
152		Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock: Combinatorial betting. SIGecom Exchanges 7(1): 61-64 (2007)
	2006
151		Lance Fortnow, Adam R. Klivans: Efficient Learning Algorithms Yield Circuit Lower Bounds. COLT 2006: 350-363
150		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
149		Lance Fortnow, Mitsunori Ogihara: Very Sparse Leaf Languages. MFCS 2006: 375-386
148		Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin: Kolmogorov Complexity with Error. STACS 2006: 137-148
147		Lance Fortnow, Adam R. Klivans: Linear Advice for Randomized Logarithmic Space. STACS 2006: 469-476
146		Richard Beigel, Lance Fortnow, William I. Gasarch: A tight lower bound for restricted pir protocols. Computational Complexity 15(1): 82-91 (2006)
145		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)
144		Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto: Low-Depth Witnesses are Easy to Find. Electronic Colloquium on Computational Complexity (ECCC) 13(125): (2006)
143		Lance Fortnow, Rakesh Vohra: The Complexity of Forecast Testing. Electronic Colloquium on Computational Complexity (ECCC) 13(149): (2006)
142		Lance Fortnow, Rahul Santhanam: Fixed-Polynomial Size Circuit Bounds. Electronic Colloquium on Computational Complexity (ECCC) 13(157): (2006)
141		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)
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: 58-72 (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

Coauthor Index

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

Colors in the list of coauthors

Last update Fri May 25 01:42:58 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page