Lance Fortnow

Lance Jeremy Fortnow (* 1963) ist ein amerikanischer Informatiker.

Fortnow studierte Mathematik und Informatik an der Cornell University (Bachelor 1985) und wurde 1989 bei Michael Sipser am Massachusetts Institute of Technology promoviert (Complexity theoretic aspects of interactive proof systems). 1989 wurde er Assistant Professor, 1994 Associate Professor und 2003 Professor für Informatik an der University of Chicago. Seit 2008 ist er Professor an der Northwestern University und Adjunct Professor am Toyota Technology Institute at Chicago und außerdem seit 2008 am Kellogg Graduate Institute of Management Science. 1996/97 war er als Fulbright-Stipendiat Gastprofessor am Centrum Wiskunde & Informatica in Amsterdam und 1999 bis 2003 Senior Scientist am NEC Research Institute in Princeton. 2001/2002 war er Gastprofessor an der Princeton University.

Zu seinen Doktoranden zählt Carsten Lund, und mit diesem und László Babai erzielte er Anfang der 1990er Jahre wichtige Fortschritte in der Komplexitätstheorie von zufallsgesteuerten Beweissystemen (Probabilistic Checkable Proofs, PCP) bzw. interaktiven Beweissystemen. Insbesondere bewiesen sie, dass die Klasse der Beweise von nicht-deterministischen Turingmaschinen mit exponentiellem Zeitaufwand in der Klasse PCP (mit polynomialer Komplexität der Fragen und der verwendeten Zufallszahlen) ist (NEXP ⊆ PCP[poly(n), poly(n)]). Die Bemühungen, die Klasse zu erweitern führten dann in den 1990er Jahren zum PCP-Theorem.

Seit den 2000er Jahren beschäftigt er sich auch mit Anwendungen der Komplexitätstheorie in den Wirtschaftswissenschaften, wo er unter anderem das Gefangenendilemma mit Duke Whang spieltheoretisch untersuchte und logarithmische Prognoseregeln für Märkte (Market Scoring Rules) von Robin Hanson.

Seit 2007 ist er Fellow der Association for Computing Machinery. Er ist Mitgründer und Herausgeber der ACM Transactions on Computation Theory.

• The Golden Ticket: P, NP, and the Search for the Impossible, Princeton University Press 2013, ISBN 0691156492.
• Fortnow: Status of P vs. NP, Comm. ACM Bd. 52, 2009, S. 78–86, Übersichtsartikel zum Status des P-NP-Problems
• Mit Steve Homer: A short history of computational complexity, Bulletin of the European Association for Theoretical Computer Science, Band 80, Juni 2003, PDF-Datei
• Mit Carsten Lund, Howard Karloff und Noam Nisan: Algebraic methods for interactive proof systems, Journal of the ACM, Band 39, 1992, S. 859–868
• Mit László Babai und Carsten Lund: Non deterministic exponential time has two prover interactive protocols, Computational Complexity, Band 1, 1991, S. 3–40

• Website (englisch)
• Blog von Fortnow über Komplexitätstheorie (englisch)