Lance Fortnow

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

Fortnow studied mathematics and computer science at Cornell University (Bachelor 1985) and in 1989 with Michael Sipser at the Massachusetts Institute of Technology PhD ( Complexity theoretic aspects of interactive proof systems). He was an Assistant Professor, Associate Professor in 1994 and 2003, professor of computer science at the University of Chicago in 1989. Since 2008 he is a professor at Northwestern University and Adjunct Professor at the Toyota Technology Institute at Chicago and since 2008 also at the Kellogg Graduate Institute of Management Science. 1996/97 he was a Fulbright Scholar Visiting Professor at the Center Wiskunde & Informatica in Amsterdam, 1999-2003 Senior Scientist at NEC Research Institute in Princeton. 2001/2002 he was a visiting professor at Princeton University.

His doctoral counts Carsten Lund, and with this and László Babai he scored early 1990s major advances in complexity theory of randomized controlled proof systems ( Probabilistic checkable proofs, PCP ) or interactive proof systems. In particular, they proved that the class of evidence of non- deterministic Turing machines with exponential time in the PCP class is ( with polynomial complexity of the issues and the random numbers used ) ( NEXP ⊆ PCP [ poly ( n ), poly (n)] ). Efforts to extend the class then led in the 1990s to the PCP Theorem.

Since the 2000s, he also deals with applications of complexity theory in economics, game theory where he studied, among others, the prisoner's dilemma with Duke Whang and logarithmic prediction rules for markets ( Market Scoring Rules) by Robin Hanson.

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

Writings

  • Fortnow status of P vs. NP, Comm.ACM Vol 52, 2009, pp. 78-86, a review 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 László Babai and Carsten Lund: Non deterministic exponential time has two prover interactive protocols, Computational Complexity, Volume 1, 1991, pp. 3-40
  • With Carsten Lund, Howard Karloff, and Noam Nisan: Algebraic methods for interactive proof systems, Journal of the ACM, Volume 39, 1992, pp. 859-868
Princeton (New Jersey) Non-deterministic Turing machine NEXPTIME PCP-Theorem Integrated Authority File
342957
de