Lance Fortnow

Fortnow has also authored a popular science book, titled The Golden Ticket: P, NP and the Search for the Impossible., which was loosely based on an article he previously wrote for CACM in 2009. In his book, Fortnow provides a non-technical introduction to the P versus NP problem and its algorithmic limitations. He further describes his book and illustrates why NP problems are so important on the Data Skeptic podcast.

Fortnow was the founding editor-in-chief of the journal ACM Transactions on Computation Theory. He was the chair of ACM SIGACT and succeeded by Paul Beame. He was the chair of the IEEE Conference on Computational Complexity from 2000 to 2006. In 2003, Fortnow began one of the first blogs devoted to theoretical computer science and has written for it since then; since 2007 he has had a co-blogger, William Gasarch. In September 2009, Fortnow brought mainstream attention to complexity theory when he published an article surveying the progress made in the P versus NP problem in the Communications of the Association of Computing Machinery.

In November 1989, Fortnow received an email from Noam Nisan showing that co-NP had multiple prover interactive proofs (MIP). With Carsten Lund and Howard Karloff, he used this result to develop an algebraic technique for the construction of interactive proof systems and prove that every language in the polynomial-time hierarchy has an interactive proof system. Their work was hardly two weeks old when Adi Shamir employed it to prove that IP=PSPACE. Quickly following up on this (January 17, 1990 less than two months after receiving Nisan's email) Fortnow, along with László Babai and Carsten Lund, proved that MIP=NEXP. These algebraic techniques were expanded further by Fortnow, Babai, Leonid Levin, and Mario Szegedy when they presented a new generic mechanism for checking computations.

Lance Fortnow received a doctorate in Applied Mathematics from MIT in 1989, supervised by Michael Sipser. Since graduation, he's served on the faculty of the University of Chicago (1989-1999, 2003-2007), Northwestern University (2008-2012), and most recently the Georgia Institute of Technology (2012–present) as chair of the School of Computer Science.

Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Science at the Illinois Institute of Technology.