Lance Fortnow

Lance Jeremy Fortnow (* 1963 ) is an American computer scientist .

Fortnow studied mathematics and computer science at Cornell University (Bachelor 1985) and received his doctorate in 1989 under Michael Sipser at the Massachusetts Institute of Technology ( Complexity theoretical aspects of interactive proof systems ). In 1989 he became Assistant Professor, 1994 Associate Professor and 2003 Professor of Computer Science at the University of Chicago . Since 2008 he has been Professor at Northwestern University and Adjunct Professor at the Toyota Technology Institute at Chicago and since 2008 at the Kellogg Graduate Institute of Management Science. In 1996/97 he was visiting professor at the Centrum Wiskunde & Informatica in Amsterdam as a Fulbright scholar and from 1999 to 2003 Senior Scientist at the NEC Research Institute in Princeton . In 2001/2002 he was visiting professor at Princeton University .

Carsten Lund is one of his doctoral students , and with him and László Babai he made important advances in the complexity theory of randomly controlled proof systems (Probabilistic Checkable Proofs, PCP) and interactive proof systems in the early 1990s . In particular, they proved that the class of the proofs of non-deterministic Turing machines with exponential expenditure of time is in the class PCP (with polynomial complexity of the questions and the random numbers used) ( NEXP ⊆ PCP [poly ( n ), poly ( n )]). Efforts to expand the class then led to the PCP theorem in the 1990s .

Since the 2000s, he has also been involved with applications of complexity theory in economics, where he examined the prisoner's dilemma with Duke Whang in game theory and logarithmic forecasting rules for markets (Market Scoring Rules) by Robin Hanson .

He has been a Fellow of the Association for Computing Machinery since 2007 . He is the co-founder and editor of ACM Transactions on Computation Theory.

Fonts

• 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 Vol. 52, 2009, pp. 78-86 , review article on the status of the P-NP problem
• With Steve Homer: A short history of computational complexity , Bulletin of the European Association for Theoretical Computer Science, Volume 80, June 2003, PDF file
• With Carsten Lund , Howard Karloff and Noam Nisan: Algebraic methods for interactive proof systems , Journal of the ACM, Volume 39, 1992, pp. 859-868
• With László Babai and Carsten Lund: Non deterministic exponential time has two prover interactive protocols , Computational Complexity, Volume 1, 1991, pp. 3-40

Web links

• Website (English)
• Blog of Fortnow on complexity theory (English)