Lance Fortnow | Academic Influence

Lance Fortnow's AcademicInfluence.com Rankings

Lance Fortnow

Computer Science

#685

World Rank

#706

Historical Rank

#370

USA Rank

Database

#2664

World Rank

#2786

Historical Rank

#555

USA Rank

computer-science Degrees

Download Badge

Computer Science

Lance Fortnow's Degrees

Bachelors Mathematics Princeton University

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Lance Fortnow Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.

(See a Problem?)

Lance Fortnow's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Algebraic methods for interactive proof systems (1990) (840)
Checking computations in polylogarithmic time (1991) (625)
Non-deterministic exponential time has two-prover interactive protocols (2005) (486)
Infeasibility of instance compression and succinct PCPs for NP (2007) (343)
Non-deterministic exponential time has two-prover interactive protocols (1990) (319)
Testing that distributions are close (2000) (303)
The status of the P versus NP problem (2009) (294)
The complexity of perfect zero-knowledge (1987) (253)
On the Power of Multi-Prover Interactive Protocols (1994) (249)
Testing random variables for independence and identity (2001) (216)
Gap-definable counting classes (1991) (204)
Recent Developments in Explicit Constructions of Extractors (2002) (201)
On the random-self-reducibility of complete sets (1991) (195)
Complexity limitations on quantum computation (1998) (181)
Computational identification of operons in microbial genomes. (2002) (152)
Testing Closeness of Discrete Distributions (2010) (150)
On the power of multi-power interactive protocols (1988) (123)
Proceedings of the 43rd annual ACM symposium on Theory of computing (2011) (113)
Gaming Prediction Markets: Equilibrium Strategies with a Market Maker (2010) (111)
A Short History of Computational Complexity (2003) (103)
Nonrelativizing separations (1998) (93)
Time-space lower bounds for satisfiability (2005) (89)
Are There Interactive Protocols for CO-NP Languages? (1988) (89)
The Role of Relativization in Complexity Theory (1994) (88)
Proceedings of the forty-third annual ACM symposium on Theory of computing (2011) (87)
Resource-Bounded Kolmogorov Complexity Revisited (1997) (79)
On oracle builder's toolkit (1993) (78)
PP is closed under truth-table reductions (1991) (77)
Complexity-Theoretic Aspects of Interactive Proof Systems (1989) (75)
ViewpointTime for computer science to grow up (2009) (73)
Complexity of combinatorial market makers (2008) (70)
One complexity theorist's view of quantum computing (2000) (67)
Hierarchy theorems for probabilistic polynomial time (2004) (65)
Time-Space Tradeoffs for Satisfiability (2000) (64)
Counting complexity (1998) (61)
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time (2005) (57)
Quantum property testing (2002) (57)
The Golden Ticket - P, NP, and the Search for the Impossible (2013) (56)
Bluffing and Strategic Reticence in Prediction Markets (2007) (53)
Computation in a distributed information market (2003) (53)
Computational depth: Concept and applications (2006) (52)
Extremes in the Degrees of Inferability (1994) (50)
Inverting onto functions (1995) (50)
An optimal procedure for gap closing in whole genome shotgun sequencing (2001) (48)
Betting boolean-style: a framework for trading in securities based on logical formulas (2003) (46)
The complexity of forecast testing (2008) (46)
Efficient learning algorithms yield circuit lower bounds (2006) (45)
Extracting Kolmogorov complexity with applications to dimension zero-one laws (2006) (43)
Sophistication Revisited (2003) (40)
Arithmetization: A new method in structural complexity theory (1991) (40)
Tolerant versus intolerant testing for Boolean properties (2005) (39)
Interactive Proof Systems and Alternating Time-Space Complexity (1991) (39)
Optimality and domination in repeated games with bounded players (1993) (39)
Time-space tradeoffs for nondeterministic computation (2000) (39)
On the Complexity of Succinct Zero-Sum Games (2005) (39)
Betting on permutations (2007) (37)
Two queries (1998) (37)
The isomorphism conjecture holds relative to an oracle (1992) (36)
Nondeterministic polynomial time versus nondeterministic logarithmic space: time-space tradeoffs for satisfiability (1997) (35)
Hierarchies for semantic classes (2005) (34)
The Complexity of Perfect Zero-Knowledge (Extended Abstract) (1987) (34)
On Resource-Bounded Instance Complexity (1996) (32)
Using autoreducibility to separate complexity classes (1995) (32)
One-sided Versus Two-sided Error in Probabilistic Computation (1999) (32)
Separating Complexity Classes Using Autoreducibility (1998) (30)
NP might not be as easy as detecting unique solutions (1997) (30)
Prediction and dimension (2002) (30)
Proceedings of the 10th ACM conference on Electronic commerce (2009) (27)
Enumerations of the Kolmogorov function (2006) (26)
Sublinear-time approximation of Euclidean minimum spanning tree (2003) (25)
A computational theory of awareness and decision making (2009) (25)
Program equilibria and discounted computation time (2009) (24)
Worst-Case Running Times for Average-Case Algorithms (2009) (23)
Derandomizing from Random Strings (2009) (23)
Complexity classes of equivalence problems revisited (2009) (23)
Proving SAT does not have small circuits with an application to the two queries problem (2003) (23)
Increasing Kolmogorov Complexity (2005) (22)
Comparing notions of full derandomization (2001) (21)
Some Results on Derandomization (2003) (20)
The Enduring Legacy of the Turing Machine (2012) (20)
A tight lower bound for restricted pir protocols (2006) (20)
Unconditional Lower Bounds against Advice (2009) (19)
The power of adaptiveness and additional queries in random-self-reductions (1992) (18)
Fixed-Polynomial Size Circuit Bounds (2009) (18)
Probabilistic computation and linear time (1989) (17)
Innovations in Computer Science - ICS 2010 (2010) (17)
Robust simulations and significant separations (2010) (17)
On coherence, random-self-reducibility, and self-correction (1996) (17)
Infinitely-Often Autoreducible Sets (2003) (16)
Kolmogorov Complexity with Error (2006) (16)
Review: Michael Sipser, Introduction to the Theory of Computation (1999) (16)
Gap-Definability as a Closure Property (1993) (15)
NP with small advice (2005) (14)
Symmetry and equivalence relations in classical and geometric complexity theory (2012) (14)
Separability and one-way functions (1994) (14)
Optimal Proof Systems and Sparse Sets (2000) (14)
One-sided Versus Two-sided Randomness (1998) (13)
Linear Advice for Randomized Logarithmic Space (2006) (13)
Six hypotheses in search of a theorem (1997) (13)
On the Power of Two-Local Random Reductions (1991) (13)
A characterization of Hash P by arithmetic straight line programs (1990) (12)
Bounding Rationality by Discounting Time (2009) (12)
Relativized Worlds with an Infinite Hierarchy (1999) (12)
Uniformly hard languages (1998) (12)
Degrees of inferability (1992) (12)
A Nearly Tight Lower Bound for Private Information Retrieval Protocols (2003) (11)
The Golden Ticket (2013) (11)
New Non-Uniform Lower Bounds for Uniform Classes (2016) (11)
Computational depth (2001) (11)
A Simple Proof of Toda's Theorem (2009) (10)
Time-Bounded Universal Distributions (2005) (9)
Low-Depth Witnesses are Easy to Find (2007) (9)
Circuit Lower Bounds à la Kolmogorov (1995) (9)
Using Depth to Capture Average-Case Complexity (2003) (9)
Generic separations (1996) (9)
Measure, Category and Learning Theory (1995) (8)
A Nearly Tight Bound for Private Information Retrieval Protocols (2003) (8)
A Characterization of #P by Straight Line Programs of Polynomials, with Applications to Interactive Proofs and Toda''s Theorem (1990) (8)
Time Hierarchies: A Survey (2007) (8)
Two oracles that force a big crunch (2002) (7)
On the Relative Sizes of Learnable Sets (1998) (7)
Repeated matching pennies with limited randomness (2011) (7)
One Bit of Advice (2003) (7)
Promise Hierarchies (2004) (7)
Nearly tight bounds for private information retrieval systems (2002) (7)
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible? (2009) (7)
Fifty years of P vs. NP and the possibility of the impossible (2021) (6)
Time-Space Tradeos for Satisability (1997) (6)
Retraction of probabilistic computation and linear time (1997) (6)
Nearly Optimal Language Compression Using Extractors (1998) (5)
Distinguishing Complexity and Symmetry of Information (1995) (5)
Beyond NP: the work and legacy of Larry Stockmeyer (2005) (5)
Inseparability and Strong Hypotheses for Disjoint NP Pairs (2009) (5)
Results on Resource-Bounded Measure (1997) (4)
Ubiquity symposium 'What is computation?': The enduring legacy of the Turing machine (2010) (4)
Beating a Finite Automaton in the Big Match (1998) (4)
The history of complexity (2002) (4)
Kolmogorov Complexity and Computational Complexity (2004) (4)
Combinatorial betting (2007) (3)
Membership Comparable and p-Selective Sets (2002) (3)
Randomized Algorithms for Dynamic Storage Load-Balancing (2016) (3)
Nondeterministic Polynomial Time versus Nondeterministic Logartithmic Space (1996) (3)
Inverting Onto Functions and Polynomial Hierarchy (2007) (3)
L-printable sets (1996) (3)
Introduction of quantum computing from the computer science perspective and reviewing activities : Quantum information technology (2003) (3)
Gap-De nability as a Closure Property ? (1992) (3)
Better Algorithms for Hybrid Circuit and Packet Switching in Data Centers (2017) (3)
Sub-linear approximation of euclidean minimum spanning tree (2005) (3)
Time-space Tradeoos for Satissability (1997) (3)
Multi-outcome and Multidimensional Market Scoring Rules (2012) (3)
Distributionally Hard Languages (2001) (3)
Resource-Bounded Instance Complexity (Extended Abstract) (1995) (2)
Easy Sets Without Easy Small Subsets (1996) (2)
A note on adaptiveness and advice in coherence (1994) (2)
The Computational Complexity Column (2003) (2)
Hierarchies Against Sublinear Advice (2014) (2)
Learning Reductions to Sparse Sets (2013) (2)
Quantized BvND: A Better Solution for Optical and Hybrid Switching in Data Center Networks (2018) (2)
My Favorite Ten Complexity Theorems of the Past Decade (1994) (2)
Prediction Markets : Equilibrium Strategies with a Market (2009) (2)
Compression Complexity (2017) (2)
Beyond P^(NP) - NEXP (1995) (2)
Are Cook and Karp ever the same? (2003) (2)
One-sided two-sided error in probabilistic computation (1999) (2)
Review of "Theory of semi-feasible algorithms" by Lane Hemaspaandra and Leen Torenvliet. Springer. (2004) (2)
2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching (2018) (2)
Using autoreducibility in separating complexity classes (1995) (2)
An Oracle Builder's Toolkit an Oracle Builder's Toolkit (1993) (1)
The infinite version of an open communication complexity problem is independent of the axioms of set theory (1994) (1)
Best First Fit (BFF): An Approach to Partially Reconfigurable Hybrid Circuit and Packet Switching (2018) (1)
Two Remarks on Self-Correctability versus Random-Self-Reducibility (1994) (1)
The complexity of forecast testing: abstract (2008) (1)
Proceedings 10th ACM Conference on Electronic Commerce (EC-2009), Stanford, California, USA, July 6--10, 2009 (2009) (1)
Loopholes (2016) (1)
The Beautiful World (2017) (1)
Nondeterministic Separations (2015) (1)
Optimality and Domination in Repeated Games (1994) (1)
Extractors for Kolmogorov Complexity (1996) (1)
Testing Closeness of Discrete Distributions Citation (2010) (1)
Multi-outcome and Multidimensional Market Scoring Rules (Manuscript) (2012) (1)
Distributionally-Hard Languages (1999) (0)
On Inverting Onto (1996) (0)
On Closure Properties of Bounded 2-sided Error Com- the Equivalence Problem for Regular Expres- Sions with Squaring Requires Exponential Space. In (1994) (0)
A Generic Separation (1993) (0)
P and NP (2017) (0)
Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (info) Self-stabilization by Tree Correction (1995) (0)
The Prehistory of P versus NP (2017) (0)
Toda ’ s Theorem , following Lance Fortnow Advanced Complexity Test (2011) (0)
Explorer Robust Simulations and Significant Separations (2011) (0)
Algebraic Methods in Computational Complexity, 10.-15. October 2004 (2005) (0)
An Oracle to which the Isomorphism Conjecture Holds (1992) (0)
A Personal View of the P versus NP Problem (2013) (0)
Complexity with Rod (2017) (0)
Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I (2009) (0)
Inseparability and Strong Hypotheses for Disjoint NP Pairs (2011) (0)
09421 Executive Summary - Algebraic Methods in Computational Complexity (2009) (0)
Pspace-hard Functions Checkable Debate Systems and Approximation Algorithms for Pspace (2007) (0)
Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421) (2021) (0)
Chapter 3 P and NP (2013) (0)
Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008: Preface (2008) (0)
Computational Complexity (2014) (0)
How Far Are We from Proving Circuit Size Lower Bounds ? (2008) (0)
Chapter 10 The Future (2013) (0)
Chapter 7 Proving P ≠ NP (2013) (0)
UvA-DARE (Digital Academic Repository) Quantum property testing (2008) (0)
Dealing with Hardness (2017) (0)
Chapter 9 Quantum (2013) (0)
Chapter 4 The Hardest Problems in NP (2013) (0)
Computer Science in Six-Tenths of a Second: What Happens After Hitting ENTER in a Google Search (2018) (0)
Worlds to Die Harder For Open Oracle Questions for the 21st Century (2021) (0)
Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008 (2008) (0)
Complexity Theory Newsflash (1996) (0)
Inverting onto functions might not be hard (2006) (0)
Two Results on Resource-bounded Measure (1996) (0)
Quantum Property TestingzHarry (2001) (0)
Chapter Notes and Sources (2013) (0)
One-sided Versus Two-sided Error in ProbabilisticComputationHarry Buhrman 1 ? and (2010) (0)
Executive Summary of Dagstuhl Seminar 07411 on Algebraic Methods in Computational Complexity October 7 to 12 , 2007 organized by Manindra Agrawal Harry Buhrman (2008) (0)
Review: Shafi Goldwasser, Silvio Micali, Charles Rackoff, The Knowledge Complexity of Interactive Proof Systems; Oded Goldreich, Silvio Micali, Avi Wigderson, J. Gruska, B. Rovan, J. Wiedermann, Proofs that Release Minimum Knowledge; Oded Goldreich, Rolf Herken, Randomness, Interactive Proofs, and Z (1991) (0)
Algebraic Methods in Computational Complexity Dagstuhl Seminar (2010) (0)
Learning Weak Reductions to Sparse Sets (2012) (0)
Matrix Multiplication and Binary Space Partitioning Trees : An Exploration (2020) (0)
Weakly Growing Context-sensitive Grammars Chicago Journal of Theoretical Computer Science (1996) (0)
Chapter 8 Secrets (2013) (0)
TWO ORACLES THAT FORCE A (2007) (0)
Executive Summary of Dagstuhl Seminar 09421 on Algebraic Methods in Computational Complexity October 11 to 16 , 2009 organized by Manindra Agrawal (2009) (0)
Edinburgh Research Explorer Unconditional Lower Bounds against Advice (2009) (0)
Chapter 1 The Golden Ticket (2013) (0)
Using Depth to Capture Average-CaseComplexityLu (2003) (0)
Very Sparse Leaf Languages (2006) (0)
Chapter 2 The Beautiful World (2013) (0)
09421 Abstracts Collection - Algebraic Methods in Computational Complexity (2009) (0)
David Stifler Johnson: A Tribute by Lance Fortnow (2016) (0)
Freestyle Dancing: Randomized Algorithms for Dynamic Storage Load-Balancing (2016) (0)
Algorithms for bandit online linear optimization (2008) (0)
Book review: of Bounded Queries in Recursion Theory by William A. Gasarch and Georgia A. Martin (Birkhauser. Boston, Basel, Berlin, 1999) (1999) (0)
My Favorite Ten Complexity Theoremsof the Past DecadeLance Fortnow ? (2010) (0)
Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007 (2008) (0)
Algebraic Methods in Computational Complexity 3 Formula Size Lower Bounds and Quantum States (2005) (0)
A Characterization of \sharp P Arithmetic Straight Line Programs (1990) (0)
Chapter 6 Dealing with Hardness (2013) (0)
Theory of Quantum Computing and Communication (2002) (0)
L-Printable Setvs (Extended Abstract) (1996) (0)
Editor’s Foreword (2004) (0)
Chapter 5 The Prehistory of P versus NP (2013) (0)
The Hardest Problems in NP (2017) (0)
Georgia Tech Faculty Panel: Perspectives on Open Access (2013) (0)

This paper list is powered by the following services:

Other Resources About Lance Fortnow

en.wikipedia.org

What Schools Are Affiliated With Lance Fortnow?

Lance Fortnow is affiliated with the following schools: