Lance Fortnow

According to our database1, Lance Fortnow authored at least 180 papers between 1987 and 2018.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks.
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.
Proceedings of the Cloud Computing - CLOUD 2018, 2018

Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching.
Proceedings of the 11th IEEE International Conference on Cloud Computing, 2018

2017
Complexity with Rod.
Proceedings of the Computability and Complexity, 2017

2016
The Golden Ticket P, NP, and the Search for the Impossible.
Bulletin of the EATCS, 2016

David Stifler Johnson: A Tribute by Lance Fortnow.
Bulletin of the EATCS, 2016

Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing.
Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016

New Non-Uniform Lower Bounds for Uniform Classes.
Proceedings of the 31st Conference on Computational Complexity, 2016

Randomized Algorithms for Dynamic Storage Load-Balancing.
Proceedings of the Seventh ACM Symposium on Cloud Computing, 2016

2015
Nondeterministic Separations.
Proceedings of the Theory and Applications of Models of Computation, 2015

2014
Computational Complexity.
Proceedings of the Computational Logic, 2014

Hierarchies Against Sublinear Advice.
Electronic Colloquium on Computational Complexity (ECCC), 2014

2013
Testing Closeness of Discrete Distributions.
J. ACM, 2013

Learning Reductions to Sparse Sets.
Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

A Personal View of the P versus NP Problem.
Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

The Golden Ticket - P, NP, and the Search for the Impossible.
Princeton University Press, ISBN: 978-0-691-15649-1, 2013

2012
The Enduring Legacy of the Turing Machine.
Comput. J., 2012

2011
Complexity classes of equivalence problems revisited.
Inf. Comput., 2011

Repeated matching pennies with limited randomness.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Robust Simulations and Significant Separations.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

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

Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
Theory Comput. Syst., 2010

Gaming Prediction Markets: Equilibrium Strategies with a Market Maker.
Algorithmica, 2010

Inseparability and Strong Hypotheses for Disjoint NP Pairs.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Bounding Rationality by Discounting Time.
Proceedings of the Innovations in Computer Science, 2010

Derandomizing from Random Strings.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

2009
Editor's Foreword.
TOCT, 2009

A Simple Proof of Toda's Theorem.
Theory of Computing, 2009

The status of the P versus NP problem.
Commun. ACM, 2009

Viewpoint - Time for computer science to grow up.
Commun. ACM, 2009

Program equilibria and discounted computation time.
Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2009), 2009

A computational theory of awareness and decision making.
Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2009), 2009

Unconditional Lower Bounds against Advice.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Unconditional Lower Bounds against Advice.
Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

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

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

Fixed-Polynomial Size Circuit Bounds.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

Worst-Case Running Times for Average-Case Algorithms.
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008
The complexity of forecast testing.
SIGecom Exchanges, 2008

Proving SAT does not have small circuits with an application to the two queries problem.
J. Comput. Syst. Sci., 2008

Infeasibility of instance compression and succinct PCPs for NP.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The complexity of forecast testing: abstract.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

Complexity of combinatorial market makers.
Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

2007
Combinatorial betting.
SIGecom Exchanges, 2007

Time Hierarchies: A Survey.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Bluffing and Strategic Reticence in Prediction Markets.
Proceedings of the Internet and Network Economics, Third International Workshop, 2007

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

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

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

Inverting Onto Functions and Polynomial Hierarchy.
Proceedings of the Computer Science, 2007

Low-Depth Witnesses are Easy to Find.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006
Computational depth: Concept and applications.
Theor. Comput. Sci., 2006

Enumerations of the Kolmogorov function.
J. Symb. Log., 2006

The Complexity of Forecast Testing.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Fixed-Polynomial Size Circuit Bounds.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Inverting onto functions might not be hard.
Electronic Colloquium on Computational Complexity (ECCC), 2006

A tight lower bound for restricted pir protocols.
Computational Complexity, 2006

Kolmogorov Complexity with Error.
Proceedings of the STACS 2006, 2006

Linear Advice for Randomized Logarithmic Space.
Proceedings of the STACS 2006, 2006

Very Sparse Leaf Languages.
Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Efficient Learning Algorithms Yield Circuit Lower Bounds.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput., 2005

Time-space lower bounds for satisfiability.
J. ACM, 2005

Time-Bounded Universal Distributions
Electronic Colloquium on Computational Complexity (ECCC), 2005

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
Electronic Colloquium on Computational Complexity (ECCC), 2005

Linear Advice for Randomized Logarithmic Space
Electronic Colloquium on Computational Complexity (ECCC), 2005

Hierarchies for semantic classes.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Beyond NP: the work and legacy of Larry Stockmeyer.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Increasing Kolmogorov Complexity.
Proceedings of the STACS 2005, 2005

NP with Small Advice.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

On the Complexity of Succinct Zero-Sum Games.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Tolerant Versus Intolerant Testing for Boolean Properties.
Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

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

Tolerant Versus Intolerant Testing for Boolean Properties
Electronic Colloquium on Computational Complexity (ECCC), 2004

NP with Small Advice
Electronic Colloquium on Computational Complexity (ECCC), 2004

Promise Hierarchies
Electronic Colloquium on Computational Complexity (ECCC), 2004

Increasing Kolmogorov Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2004

Kolmogorov Complexity with Error
Electronic Colloquium on Computational Complexity (ECCC), 2004

Enumerations of the Kolmogorov Function
Electronic Colloquium on Computational Complexity (ECCC), 2004

On the complexity of succinct zero-sum games
Electronic Colloquium on Computational Complexity (ECCC), 2004

Hierarchy Theorems for Probabilistic Polynomial Time.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

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

2003
One complexity theorist's view of quantum computing.
Theor. Comput. Sci., 2003

An oracle builder's toolkit.
Inf. Comput., 2003

A Nearly Tight Bound for Private Information Retrieval Protocols
Electronic Colloquium on Computational Complexity (ECCC), 2003

A Short History of Computational Complexity.
Bulletin of the EATCS, 2003

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

One Bit of Advice.
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.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Quantum property testing.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Betting boolean-style: a framework for trading in securities based on logical formulas.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Computation in a distributed information market.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Infinitely-Often Autoreducible Sets.
Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Sophistication Revisited.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Using Depth to Capture Average-Case Complexity.
Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

Proving SAT does not have Small Circuits with an Application to the Two.
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Are Cook and Karp Ever the Same?
Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002
Prediction and Dimension.
Proceedings of the Computational Learning Theory, 2002

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

2001
Resource-Bounded Kolmogorov Complexity Revisited.
SIAM J. Comput., 2001

Guest Editor's Foreword.
J. Comput. Syst. Sci., 2001

Two oracles that force a big crunch.
Computational Complexity, 2001

An optimal procedure for gap closing in whole genome shotgun sequencing.
Proceedings of the Fifth Annual International Conference on Computational Biology, 2001

Testing Random Variables for Independence and Identity.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Comparing Notions of Full Derandomization.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

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

Diagonalization.
Current Trends in Theoretical Computer Science, 2001

2000
One complexity theorist's view of quantum computing.
Electr. Notes Theor. Comput. Sci., 2000

Separating Complexity Classes Using Autoreducibility.
SIAM J. Comput., 2000

Time-Space Tradeoffs for Satisfiability.
J. Comput. Syst. Sci., 2000

Time-Space Tradeoffs for Nondeterministic Computation
Electronic Colloquium on Computational Complexity (ECCC), 2000

Diagonalization.
Bulletin of the EATCS, 2000

Optimal Proof Systems and Sparse Sets.
Proceedings of the STACS 2000, 2000

Testing that distributions are close.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Time-Space Tradeoffs for Nondeterministic Computation.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

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

Relativized Worlds with an Infinite Hierarchy.
Inf. Process. Lett., 1999

One-sided Versus Two-sided Error in Probabilistic Computation.
Proceedings of the STACS 99, 1999

Distributionally-Hard Languages.
Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998
On the Relative Sizes of Learnable Sets.
Theor. Comput. Sci., 1998

L-Printable Sets.
SIAM J. Comput., 1998

Beating a Finite Automaton in the Big Match.
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.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Nearly Optimal Language Compression Using Extractors.
Proceedings of the STACS 98, 1998

Complexity Limitations on Quantum Computation.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

Uniformly Hard Languages.
Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

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

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

1997
Retraction of Probabilistic Computation and Linear Time.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Resource-Bounded Kolmogorov Complexity Revisited.
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.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

Nondeterministic Polynomial Time versus Nondeterministic Logarithmic Space: Time-Space Tradeoffs for Satisfiability.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

Six Hypotheses in Search of a Theorem.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
On Resource-Bounded Instance Complexity.
Theor. Comput. Sci., 1996

Complexity Theory Newsflash.
SIGACT News, 1996

The Isomorphism Conjecture Holds Relative to an Oracle.
SIAM J. Comput., 1996

L-Printable Sets.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Inverting Onto Functions.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

On Coherence, Random-self-reducibility, and Self-correction.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Circuit Lower Bounds à la Kolmogorov.
Inf. Comput., 1995

Resource-Bounded Instance Complexity (Extended Abstract).
STACS, 1995

Beyond P^(NP) - NEXP.
STACS, 1995

Measure, Category and Learning Theory.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Using Autoreducibility to Separate Complexity Classes.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994
On the Power of Multi-Prover Interactive Protocols.
Theor. Comput. Sci., 1994

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

My Favorite Ten Complexity Theorems of the Past Decade
Electronic Colloquium on Computational Complexity (ECCC), 1994

The Role of Relativization in Complexity Theory.
Bulletin of the EATCS, 1994

Extremes in the Degrees of Inferability.
Ann. Pure Appl. Logic, 1994

Optimality and domination in repeated games with bounded players.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Separability and One-Way Functions.
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

My Favorite Ten Complexity Theorems of the Past Decade.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

Generic Separations.
Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993
Random-Self-Reducibility of Complete Sets.
SIAM J. Comput., 1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Computational Complexity, 1993

Gap-Definability as a Closure Property.
Proceedings of the STACS 93, 1993

An Oarcle Builder's Toolkit.
Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992
Algebraic Methods for Interactive Proof Systems.
J. ACM, 1992

Addendum to Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity, 1992

The Isomorphism Conjecture Holds Relative to an Oracle
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

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

The Power of Adaptiveness and Additional Queries in Random-Self-Reductions.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Non-Deterministic Exponential Time has Two-Prover Interactive Protocols.
Computational Complexity, 1991

Arithmetization: A New Method in Structural Complexity Theory.
Computational Complexity, 1991

Checking Computations in Polylogarithmic Time
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Interactive Proof Systems and Alternating Time-Space Complexity.
Proceedings of the STACS 91, 1991

PP is Closed Under Truth-Table Reductions.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

Gap-Definable Counting Classes.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

On the Random-Self-Reducibility of Complete Sets.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

On the Power of Two-Local Random Reductions.
Proceedings of the Advances in Cryptology, 1991

1990
Algebraic Methods for Interactive Proof Systems
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

A Characterization of \sharp P Arithmetic Straight Line Programs
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Errata for On the Power of Multi-Prover Interactive Protocols.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989
Probabilistic Computation and Linear Time
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
Are There Interactive Protocols for CO-NP Languages?
Inf. Process. Lett., 1988

On the power of multi-power interactive protocols.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
The Complexity of Perfect Zero-Knowledge (Extended Abstract)
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

The complexity of perfect zero-knowledge.
Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987


  Loading...