Lance Fortnow

According to our database, Lance Fortnow authored at least 169 papers between 1987 and 2022.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2022

Computational Complexity.

Lance Fortnow

Bull. EATCS, 2022

Fifty years of P vs. NP and the possibility of the impossible.

Lance Fortnow

Commun. ACM, 2022

2021

Worlds to Die Harder For Open Oracle Questions for the 21st Century.

Lance Fortnow

SIGACT News, 2021

2020

Matrix Multiplication and Binary Space Partitioning Trees : An Exploration.

C. N. P. Slagle, Lance Fortnow

CoRR, 2020

2018

Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks.

Liang Liu, Jun (Jim) Xu, Lance Fortnow

Proceedings of the 11th IEEE/ACM International Conference on Utility and Cloud Computing, 2018

2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching.

Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow

Proceedings of the Cloud Computing - CLOUD 2018, 2018

Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching.

Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow

Proceedings of the 11th IEEE International Conference on Cloud Computing, 2018

2017

Robust simulations and significant separations.

Lance Fortnow, Rahul Santhanam

Inf. Comput., 2017

Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers.

Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow

CoRR, 2017

Compression Complexity.

Stephen A. Fenner, Lance Fortnow

CoRR, 2017

Complexity with Rod.

Lance Fortnow

Proceedings of the Computability and Complexity, 2017

2016

The Golden Ticket P, NP, and the Search for the Impossible.

Lance Fortnow

Bull. EATCS, 2016

David Stifler Johnson: A Tribute by Lance Fortnow.

Lance Fortnow

Bull. EATCS, 2016

Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing.

Liang Liu, Yating Wang, Lance Fortnow, Jin Li, Jun (Jim) Xu

Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

New Non-Uniform Lower Bounds for Uniform Classes.

Lance Fortnow, Rahul Santhanam

Proceedings of the 31st Conference on Computational Complexity, 2016

Randomized Algorithms for Dynamic Storage Load-Balancing.

Liang Liu, Lance Fortnow, Jin Li, Yating Wang, Jun (Jim) Xu

Proceedings of the Seventh ACM Symposium on Cloud Computing, 2016

2015

Nondeterministic Separations.

Lance Fortnow

Proceedings of the Theory and Applications of Models of Computation, 2015

2014

Computational Complexity.

Lance Fortnow, Steven Homer

Proceedings of the Computational Logic, 2014

Hierarchies Against Sublinear Advice.

Lance Fortnow, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2014

2013

Testing Closeness of Discrete Distributions.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

J. ACM, 2013

Learning Reductions to Sparse Sets.

Harry Buhrman, Lance Fortnow, John M. Hitchcock, Bruno Loff

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

A Personal View of the P versus NP Problem.

Lance Fortnow

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

The Golden Ticket - P, NP, and the Search for the Impossible.

Lance Fortnow

Princeton University Press, ISBN: 978-0-691-15649-1, 2013

2012

Inseparability and Strong Hypotheses for Disjoint NP Pairs.

Lance Fortnow, Jack H. Lutz, Elvira Mayordomo

Theory Comput. Syst., 2012

Multi-outcome and Multidimensional Market Scoring Rules

Lance Fortnow, Rahul Sami

CoRR, 2012

The Enduring Legacy of the Turing Machine.

Lance Fortnow

Comput. J., 2012

Low-Depth Witnesses are Easy to Find.

Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Comput. Complex., 2012

2011

Infeasibility of instance compression and succinct PCPs for NP.

Lance Fortnow, Rahul Santhanam

J. Comput. Syst. Sci., 2011

Complexity classes of equivalence problems revisited.

Lance Fortnow, Joshua A. Grochow

Inf. Comput., 2011

Repeated matching pennies with limited randomness.

Michele Budinich, Lance Fortnow

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

2010

Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine.

Lance Fortnow

Ubiquity, 2010

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin

Theory Comput. Syst., 2010

Gaming Prediction Markets: Equilibrium Strategies with a Market Maker.

Yiling Chen, Stanko Dimitrov, Rahul Sami, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen

Algorithmica, 2010

Bounding Rationality by Discounting Time.

Lance Fortnow, Rahul Santhanam

Proceedings of the Innovations in Computer Science, 2010

Derandomizing from Random Strings.

Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009

Editor's Foreword.

Lance Fortnow

ACM Trans. Comput. Theory, 2009

A Simple Proof of Toda's Theorem.

Lance Fortnow

Theory Comput., 2009

Sophistication Revisited.

Luis Filipe Coelho Antunes, Lance Fortnow

Theory Comput. Syst., 2009

Efficient learning algorithms yield circuit lower bounds.

Lance Fortnow, Adam R. Klivans

J. Comput. Syst. Sci., 2009

Unconditional Lower Bounds against Advice.

Harry Buhrman, Lance Fortnow, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2009

The status of the P versus NP problem.

Lance Fortnow

Commun. ACM, 2009

Viewpoint - Time for computer science to grow up.

Lance Fortnow

Commun. ACM, 2009

Program equilibria and discounted computation time.

Lance Fortnow

Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2009), 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Fixed-Polynomial Size Circuit Bounds.

Lance Fortnow, Rahul Santhanam, Ryan Williams

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Worst-Case Running Times for Average-Case Algorithms.

Luis Filipe Coelho Antunes, Lance Fortnow

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Quantum Property Testing.

Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig

SIAM J. Comput., 2008

Proving SAT does not have small circuits with an application to the two queries problem.

Lance Fortnow, Aduri Pavan, Samik Sengupta

J. Comput. Syst. Sci., 2008

A Computational Theory of Awareness and Decision Making.

Nikhil R. Devanur, Lance Fortnow

Electron. Colloquium Comput. Complex., 2008

On the Complexity of Succinct Zero-Sum Games.

Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans

Comput. Complex., 2008

The complexity of forecast testing: abstract.

Lance Fortnow, Rakesh Vohra

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Complexity of combinatorial market makers.

Yiling Chen, Lance Fortnow, Nicolas S. Lambert, David M. Pennock, Jennifer Wortman

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

2007

Combinatorial betting.

Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock

SIGecom Exch., 2007

Time Hierarchies: A Survey.

Lance Fortnow, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2007

Bluffing and Strategic Reticence in Prediction Markets.

Yiling Chen, Daniel M. Reeves, David M. Pennock, Robin D. Hanson, Lance Fortnow, Rica Gonen

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Betting on permutations.

Yiling Chen, Lance Fortnow, Evdokia Nikolova, David M. Pennock

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.

Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

07411 Executive Summary -- Algebraic Methods in Computational Complexity.

Manindra Agrawal, Harry Buhrman, Lance Fortnow, Thomas Thierauf

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

Inverting Onto Functions and Polynomial Hierarchy.

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin

Proceedings of the Computer Science, 2007

2006

Tolerant Versus Intolerant Testing for Boolean Properties.

Eldar Fischer, Lance Fortnow

Theory Comput., 2006

Computational depth: Concept and applications.

Luis Antunes, Lance Fortnow, Dieter van Melkebeek, N. V. Vinodchandran

Theor. Comput. Sci., 2006

Infinitely-Often Autoreducible Sets.

Richard Beigel, Lance Fortnow, Frank Stephan

SIAM J. Comput., 2006

Enumerations of the Kolmogorov function.

Richard Beigel, Harry Buhrman, Peter A. Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

J. Symb. Log., 2006

The Complexity of Forecast Testing.

Lance Fortnow, Rakesh Vohra

Electron. Colloquium Comput. Complex., 2006

Fixed-Polynomial Size Circuit Bounds.

Lance Fortnow, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2006

Inverting onto functions might not be hard.

Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2006

A tight lower bound for restricted pir protocols.

Richard Beigel, Lance Fortnow, William I. Gasarch

Comput. Complex., 2006

Very Sparse Leaf Languages.

Lance Fortnow, Mitsunori Ogihara

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

2005

Computation in a distributed information market.

Joan Feigenbaum, Lance Fortnow, David M. Pennock, Rahul Sami

Theor. Comput. Sci., 2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

SIAM J. Comput., 2005

Some Results on Derandomization.

Harry Buhrman, Lance Fortnow, Aduri Pavan

Theory Comput. Syst., 2005

Prediction and dimension.

Lance Fortnow, Jack H. Lutz

J. Comput. Syst. Sci., 2005

Time-space lower bounds for satisfiability.

Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, Anastasios Viglas

J. ACM, 2005

Time-Bounded Universal Distributions

Lance Fortnow, Luis Antunes

Electron. Colloquium Comput. Complex., 2005

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang

Electron. Colloquium Comput. Complex., 2005

Linear Advice for Randomized Logarithmic Space

Lance Fortnow, Adam R. Klivans

Electron. Colloquium Comput. Complex., 2005

Betting Boolean-style: a framework for trading in securities based on logical formulas.

Lance Fortnow, Joe Kilian, David M. Pennock, Michael P. Wellman

Decis. Support Syst., 2005

Hierarchies for semantic classes.

Lance Fortnow, Rahul Santhanam, Luca Trevisan

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Beyond NP: the work and legacy of Larry Stockmeyer.

Lance Fortnow

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer.

Lance Fortnow

SIGACT News, 2004

NP with Small Advice

Lance Fortnow, Adam R. Klivans

Electron. Colloquium Comput. Complex., 2004

Promise Hierarchies

Lance Fortnow, Rahul Santhanam, Luca Trevisan

Electron. Colloquium Comput. Complex., 2004

Increasing Kolmogorov Complexity

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2004

Kolmogorov Complexity with Error

Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2004

Hierarchy Theorems for Probabilistic Polynomial Time.

Lance Fortnow, Rahul Santhanam

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

04421 Abstracts Collection - Algebraic Methods in Computational Complexity.

Harry Buhrman, Lance Fortnow, Thomas Thierauf

Proceedings of the Algebraic Methods in Computational Complexity, 10.-15. October 2004, 2004

2003

Uniformly hard languages.

Rodney G. Downey, Lance Fortnow

Theor. Comput. Sci., 2003

Inverting onto functions.

Stephen A. Fenner, Lance Fortnow, Ashish V. Naik, John D. Rogers

Inf. Comput., 2003

An oracle builder's toolkit.

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li

Inf. Comput., 2003

A Nearly Tight Bound for Private Information Retrieval Protocols

Richard Beigel, Lance Fortnow, William I. Gasarch

Electron. Colloquium Comput. Complex., 2003

A Short History of Computational Complexity.

Lance Fortnow, Steven Homer

Bull. EATCS, 2003

One Bit of Advice.

Harry Buhrman, Richard Chang, Lance Fortnow

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Using Depth to Capture Average-Case Complexity.

Luis Antunes, Lance Fortnow, N. V. Vinodchandran

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Proving SAT does not have Small Circuits with an Application to the Two.

Lance Fortnow, Aduri Pavan, Samik Sengupta

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Are Cook and Karp Ever the Same?

Richard Beigel, Lance Fortnow

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Separability and one-way functions.

Lance Fortnow, John D. Rogers

Comput. Complex., 2002

The History of Complexity.

Lance Fortnow

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Resource-Bounded Kolmogorov Complexity Revisited.

Harry Buhrman, Lance Fortnow, Sophie Laplante

SIAM J. Comput., 2001

Distributionally Hard Languages.

Lance Fortnow, Aduri Pavan, Alan L. Selman

Theory Comput. Syst., 2001

Guest Editor's Foreword.

Lance Fortnow

J. Comput. Syst. Sci., 2001

Two oracles that force a big crunch.

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Leen Torenvliet

Comput. Complex., 2001

An optimal procedure for gap closing in whole genome shotgun sequencing.

Richard Beigel, Noga Alon, Simon Kasif, Mehmet Serkan Apaydin, Lance Fortnow

Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Testing Random Variables for Independence and Identity.

Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Comparing Notions of Full Derandomization.

Lance Fortnow

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Computational Depth.

Luis Antunes, Lance Fortnow, Dieter van Melkebeek

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Diagonalization.

Lance Fortnow

Proceedings of the Current Trends in Theoretical Computer Science, 2001

2000

One complexity theorist's view of quantum computing.

Lance Fortnow

Proceedings of the Computing: the Australasian Theory Symposium, 2000

Separating Complexity Classes Using Autoreducibility.

Harry Buhrman, Lance Fortnow, Dieter van Melkebeek, Leen Torenvliet

SIAM J. Comput., 2000

Time-Space Tradeoffs for Satisfiability.

Lance Fortnow

J. Comput. Syst. Sci., 2000

Time-Space Tradeoffs for Nondeterministic Computation

Lance Fortnow, Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2000

Diagonalization.

Lance Fortnow

Bull. EATCS, 2000

Optimal Proof Systems and Sparse Sets.

Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek

Proceedings of the STACS 2000, 2000

Testing that distributions are close.

Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, Patrick White

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Book review: of Bounded Queries in Recursion Theory by William A. Gasarch and Georgia A. Martin (Birkhauser. Boston, Basel, Berlin, 1999).

Lance Fortnow

SIGACT News, 1999

Complexity Limitations on Quantum Computation.

Lance Fortnow, John D. Rogers

J. Comput. Syst. Sci., 1999

Two Queries.

Harry Buhrman, Lance Fortnow

J. Comput. Syst. Sci., 1999

Relativized Worlds with an Infinite Hierarchy.

Lance Fortnow

Inf. Process. Lett., 1999

One-sided Versus Two-sided Error in Probabilistic Computation.

Harry Buhrman, Lance Fortnow

Proceedings of the STACS 99, 1999

1998

On the Relative Sizes of Learnable Sets.

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan

Theor. Comput. Sci., 1998

L-Printable Sets.

Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney

SIAM J. Comput., 1998

On Coherence, Random-Self-Reducibility, and Self-Correction.

Joan Feigenbaum, Lance Fortnow, Sophie Laplante, Ashish V. Naik

Comput. Complex., 1998

Beating a Finite Automaton in the Big Match.

Lance Fortnow, Peter G. Kimmel

Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-98), 1998

NP Might Not Be As Easy As Detecting Unique Solutions.

Richard Beigel, Harry Buhrman, Lance Fortnow

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Nearly Optimal Language Compression Using Extractors.

Lance Fortnow, Sophie Laplante

Proceedings of the STACS 98, 1998

Nonrelativizing Separations.

Harry Buhrman, Lance Fortnow, Thomas Thierauf

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Retraction of Probabilistic Computation and Linear Time.

Lance Fortnow, Michael Sipser

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Resource-Bounded Kolmogorov Complexity Revisited.

Harry Buhrman, Lance Fortnow

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

Results on Resource-Bounded Measure.

Harry Buhrman, Stephen A. Fenner, Lance Fortnow

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability.

Lance Fortnow

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Six Hypotheses in Search of a Theorem.

Harry Buhrman, Lance Fortnow, Leen Torenvliet

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

On Resource-Bounded Instance Complexity.

Lance Fortnow, Martin Kummer

Theor. Comput. Sci., 1996

Complexity Theory Newsflash.

Stephen A. Fenner, Lance Fortnow, William I. Gasarch

SIGACT News, 1996

The Isomorphism Conjecture Holds Relative to an Oracle.

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz

SIAM J. Comput., 1996

Generic Separations.

Lance Fortnow, Tomoyuki Yamakami

J. Comput. Syst. Sci., 1996

PP is Closed Under Truth-Table Reductions.

Lance Fortnow, Nick Reingold

Inf. Comput., 1996

Gap-Definability as a Closure Property.

Stephen A. Fenner, Lance Fortnow, Lide Li

Inf. Comput., 1996

L-Printable Sets.

Lance Fortnow, Judy Goldsmith, Stephen R. Mahaney

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Circuit Lower Bounds à la Kolmogorov.

Lance Fortnow, Sophie Laplante

Inf. Comput., 1995

Resource-Bounded Instance Complexity (Extended Abstract).

Lance Fortnow, Martin Kummer

Proceedings of the STACS 95, 1995

Beyond P^(NP) - NEXP.

Stephen A. Fenner, Lance Fortnow

Proceedings of the STACS 95, 1995

Measure, Category and Learning Theory.

Lance Fortnow, Rusins Freivalds, William I. Gasarch, Martin Kummer, Stuart A. Kurtz, Carl H. Smith, Frank Stephan

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Using Autoreducibility to Separate Complexity Classes.

Harry Buhrman, Lance Fortnow, Leen Torenvliet

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

On the Power of Multi-Prover Interactive Protocols.

Lance Fortnow, John Rompel, Michael Sipser

Theor. Comput. Sci., 1994

The infinite version of an open communication complexity problem is independent of the axioms of set theory.

Lance Fortnow, Stuart A. Kurtz, Duke Whang

SIGACT News, 1994

Gap-Definable Counting Classes.

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz

J. Comput. Syst. Sci., 1994

My Favorite Ten Complexity Theorems of the Past Decade

Lance Fortnow

Electron. Colloquium Comput. Complex., 1994

The Role of Relativization in Complexity Theory.

Lance Fortnow

Bull. EATCS, 1994

The Power of Adaptiveness and Additional Queries in Random-Self-Reductions.

Joan Feigenbaum, Lance Fortnow, Carsten Lund, Daniel A. Spielman

Comput. Complex., 1994

Extremes in the Degrees of Inferability.

Lance Fortnow, William I. Gasarch, Sanjay Jain, Efim B. Kinber, Martin Kummer, Stuart A. Kurtz, Mark Pleszkovich, Theodore A. Slaman, Robert Solovay, Frank Stephan

Ann. Pure Appl. Log., 1994

Optimality and domination in repeated games with bounded players.

Lance Fortnow, Duke Whang

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Interactive Proof Systems and Alternating Time-Space Complexity.

Lance Fortnow, Carsten Lund

Theor. Comput. Sci., 1993

Random-Self-Reducibility of Complete Sets.

Joan Feigenbaum, Lance Fortnow

SIAM J. Comput., 1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.

László Babai, Lance Fortnow, Noam Nisan, Avi Wigderson

Comput. Complex., 1993

An Oarcle Builder's Toolkit.

Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, Lide Li

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Algebraic Methods for Interactive Proof Systems.

Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan

J. ACM, 1992

On the Power of Two-Local Random Reductions.

Lance Fortnow, Mario Szegedy

Inf. Process. Lett., 1992

Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.

László Babai, Lance Fortnow, Carsten Lund

Comput. Complex., 1992

Degrees of Inferability.

Peter Cholak, Efim B. Kinber, Rodney G. Downey, Martin Kummer, Lance Fortnow, Stuart A. Kurtz, William I. Gasarch, Theodore A. Slaman

Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, 1992

1991

Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.

László Babai, Lance Fortnow, Carsten Lund

Comput. Complex., 1991

Arithmetization: A New Method in Structural Complexity Theory.

László Babai, Lance Fortnow

Comput. Complex., 1991

Checking Computations in Polylogarithmic Time

László Babai, Lance Fortnow, Leonid A. Levin, Mario Szegedy

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

A Characterization of \sharp P Arithmetic Straight Line Programs

László Babai, Lance Fortnow

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Errata for On the Power of Multi-Prover Interactive Protocols.

Lance Fortnow, John Rompel, Michael Sipser

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

The Complexity of Perfect Zero-Knowledge.

Lance Fortnow

Adv. Comput. Res., 1989

1988

Are There Interactive Protocols for CO-NP Languages?

Lance Fortnow, Michael Sipser

Inf. Process. Lett., 1988

On the power of multi-power interactive protocols.

Lance Fortnow, John Rompel, Michael Sipser

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

The Complexity of Perfect Zero-Knowledge (Extended Abstract)

Lance Fortnow

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987