Lance Fortnow

Last updated
Lance Fortnow
BornAugust 15, 1963 (1963-08-15) (age 60)
NationalityAmerican
Alma mater Cornell University
Massachusetts Institute of Technology
Known for Interactive proofs
Awards ACM Fellow, NSF Presidential Faculty Fellow, Fulbright Scholar, Nerode Prize
Scientific career
Fields Computer science
Institutions Illinois Institute of Technology
Georgia Tech
Northwestern University
University of Chicago
Doctoral advisor Michael Sipser
Doctoral students Carsten Lund
Website http://lance.fortnow.com/
http://blog.computationalcomplexity.org/

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

Contents

Biography

Lance Fortnow received a doctorate in applied mathematics from MIT in 1989, [1] supervised by Michael Sipser. Since graduation, he has been on the faculty of the University of Chicago (1989–1999, 2003–2007), Northwestern University (2008–2012) and the Georgia Institute of Technology (2012–2019) as chair of the School of Computer Science. [2] [3]

Fortnow was the founding editor-in-chief of the journal ACM Transactions on Computation Theory in 2009. [4] He was the chair of ACM SIGACT [5] and succeeded by Paul Beame. He was the chair of the IEEE Conference on Computational Complexity [6] from 2000 to 2006. In 2002, he began one of the first blogs devoted to theoretical computer science [7] 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 Communications of the Association for Computing Machinery . [8]

Work

In his many publications, Fortnow has contributed important results to the field of computational complexity. While still a graduate student at MIT, Fortnow showed that there are no perfect zero-knowledge protocols for NP-complete languages unless the polynomial hierarchy collapses. [9] With Michael Sipser, he also demonstrated that relative to a specific oracle there exists a language in co-NP that does not have an interactive protocol. [10]

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. [11] Their work was hardly two weeks old when Adi Shamir employed it to prove that IP=PSPACE. [12] 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. [13] These algebraic techniques were expanded further by Fortnow, Babai, Leonid Levin and Mario Szegedy when they presented a new generic mechanism for checking computations. [14]

Fortnow has continued to publish on a variety of topics in the field of computational complexity including derandomization, sparse languages, and oracle machines. Fortnow has also published on quantum computing, game theory, genome sequencing and economics.

Fortnow's work in economics includes work in game theory, optimal strategies and prediction. With Duke Whang, he has examined the classic game theory problem of the prisoner's dilemma, extending the problem so that the dilemma is posed sequentially an infinite number of times. They investigated what strategies the players should take given the constraints that they draw their strategies from computationally bounded sets and introduce “grace periods” to prevent the dominance of vengeful strategies. [15] Fortnow also examined the logarithmic market scoring rule (LMSR) with market makers. He helped to show that LMSR pricing is #P-hard and proposed an approximation technique for pricing permutation markets. [16] He has also contributed to a study of the behavior of informed traders working with LMSR market makers. [17]

Fortnow has also written a popular science book, The Golden Ticket: P, NP and the Search for the Impossible, [18] which was loosely based on an article he had written for CACM in 2009. [19] 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. [20]

Awards and honors

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

<span class="mw-page-title-main">Interactive proof system</span>

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof, as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public. Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

In computational complexity theory, the complexity class ⊕P is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.

<span class="mw-page-title-main">IP (complexity)</span>

In computational complexity theory, the class IP is the class of problems solvable by an interactive proof system. It is equal to the class PSPACE. The result was established in a series of papers: the first by Lund, Karloff, Fortnow, and Nisan showed that co-NP had multiple prover interactive proofs; and the second, by Shamir, employed their technique to establish that IP=PSPACE. The result is a famous example where the proof does not relativize.

In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.

Richard Jay Lipton is an American computer scientist who is Associate Dean of Research, Professor, and the Frederick G. Storey Chair in Computing in the College of Computing at the Georgia Institute of Technology. He has worked in computer science theory, cryptography, and DNA computing.

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Bedminster, New Jersey, United States.

In computational complexity theory, the class QIP is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language and cannot convince the verifier to accept when the input is not in the language. In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than 2/3, and if the input is not in the language, the verifier should be reject with probability greater than 2/3. In IP, the verifier is like a BPP machine. In QIP, the communication between the prover and verifier is quantum, and the verifier can perform quantum computation. In this case the verifier is like a BQP machine.

<span class="mw-page-title-main">John Watrous (computer scientist)</span> Theoretical computer scientist

John Harrison Watrous is the Technical Director of IBM Quantum Education at IBM and was a professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian Institute for Advanced Research. He was a faculty member in the Department of Computer Science at the University of Calgary from 2002 to 2006 where he held a Canada Research Chair in quantum computing.

Verifiable computing enables a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted users in projects such as SETI@home and also to the growing desire to enable computationally-weak devices to outsource computational tasks to a more powerful computation service, as in cloud computing. The concept dates back to work by Babai et al., and has been studied under various terms, including "checking computations", "delegating computations", "certified computation", and verifiable computing. The term verifiable computing itself was formalized by Rosario Gennaro, Craig Gentry, and Bryan Parno, and echoes Micali's "certified computation".

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

References

  1. ↑ Lance Fortnow at the Mathematics Genealogy Project
  2. ↑ "College of Computing Hires Fortnow, Anton to Lead Schools" (Press release). Georgia Tech College of Computing. March 19, 2012. Retrieved October 4, 2012.
  3. ↑ Northwestern University Electrical Engineering and Computer Science Department Faculty
  4. ↑ ACM Transactions on Computation Theory
  5. ↑ ACM SIGACT
  6. ↑ IEEE Conference on Computational Complexity
  7. ↑ Computational Complexity weblog
  8. ↑ J. Markoff, "Prizes Aside, the P-NP Puzzler Has Consequences" The New York Times, October 7, 2009(subscription required)
    - L. Fortnow, "The Status of the P Versus NP Problem", Communications of the ACM 9 (2009)
  9. ↑ L. Fortnow, "The complexity of perfect zero-knowledge" in S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 327-343. JAI Press, Greenwich, 1989
  10. ↑ L. Fortnow and M. Sipser, "Are there interactive protocols for co-NP languages?", Information Processing Letters , 28:249-251, 1988
  11. ↑ C. Lund, L. Fortnow, H. Karloff, and N. Nisan, "Algebraic methods for interactive proof systems", Journal of the ACM, 39(4):859-868, 1992
  12. ↑ A. Shamir, "IP = PSPACE", Journal of the ACM39(4):869-877, 1992
  13. ↑ L. Babai, L. Fortnow, and C. Lund, "Nondeterministic exponential time has two-prover interactive protocols", Computational Complexity, 1(1):3-40, 1991
  14. ↑ L. Babai, L. Fortnow, L. Levin, and M. Szegedy. "Checking computations in polylogarithmic time", in Proceedings of the 23rd ACM Symposium on the Theory of Computing , pages 21-31. ACM, New York, 1991
  15. ↑ L. Fortnow and D. Whang, "Optimality and domination in repeated games with bounded players", in Proceedings of the 26th ACM Symposium on the Theory of Computing, pages 741-749. ACM, New York, 1994
  16. ↑ Y. Chen, L. Fortnow, N. Lambert, D. Pennock and J. Wortman, "Complexity of combinatorial market makers", in Proceedings of the 9th ACM Conference on Electronic Commerce, pages 190-199. ACM, New York, 2008
  17. ↑ Y. Chen, S. Dimitrov, R. Sami, D. Reeves, D. Pennock, R. Hanson, L. Fortnow, and R. Gonen, "Gaming prediction markets: Equilibrium strategies with a market maker", Algorithmica, 2009
  18. ↑ Fortnow, Lance The Golden Ticket: P, NP and the Search for the Impossible ., Princeton University Press, 2013
  19. ↑ Fortnow, Lance, "The Status of the P Versus NP Problem", review article in Communications of the ACM, 52(9): 78-86, September 2009
  20. ↑ "P vs NP", Data Skeptic, 2017
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.