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.