Lance Fortnow
Encyclopedia
Lance Jeremy Fortnow is a computer scientist
in the field of computational complexity
and its applications, notable for producing major results on interactive proof systems.
. He has been a professor in the Electrical Engineering and Computer Science Department at Northwestern University since 2008. Fortnow is founding editor-in-chief of the journal ACM Transaction on Computation Theory. He is chair of ACM SIGACT and was 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. 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.
. While still a grad student at MIT, Fortnow showed that there are no perfect zero-knowledge protocols
for NP-complete languages unless the polynomial hierarchy
collapses. 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.
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.
Since this time Fortnow has continued to publish on a variety of topics in the field of computational complexity including derandomization, sparse language
s, and oracle machine
s. Fortnow has also published on quantum computing, game theory
, genome sequencing, and economics
.
Lance Fortnow's work in economics includes work in game theory, optimal strategies, and prediction. With Duke Whang, Fortnow 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. Fortnow also examined the logarithmic
market scoring rule (LMSR) with market makers. He helped to show that LMSR pricing is #P-hard and propose an appoximation technique for pricing permutation markets. He has also contributed to an examination the behavior of informed traders working with LMSR market makers.
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
in the field of computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
and its applications, notable for producing major results on interactive proof systems.
Biography
Lance Fortnow received a Ph.D. in Applied Mathematics from MIT in 1989, supervised by Michael SipserMichael Sipser
Michael Fredric Sipser is a professor of Applied Mathematics in the Theory of Computation Group at the Massachusetts Institute of Technology. He received his Ph.D. in 1980 from the University of California, Berkeley under the direction of Manuel Blum....
. He has been a professor in the Electrical Engineering and Computer Science Department at Northwestern University since 2008. Fortnow is founding editor-in-chief of the journal ACM Transaction on Computation Theory. He is chair of ACM SIGACT and was 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. 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.
Work
In his many publications, Fortnow has contributed important results to the field of computational complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
. While still a grad student at MIT, Fortnow showed that there are no perfect zero-knowledge protocols
Protocol (object-oriented programming)
In object-oriented programming, a protocol or interface is a common means for unrelated objects to communicate with each other. These are definitions of methods and values which the objects agree upon in order to cooperate....
for NP-complete languages unless the polynomial hierarchy
Polynomial hierarchy
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines...
collapses. 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.
In November 1989, Fortnow received an email from Noam Nisan showing that co-NP had multiple prover interactive proofs (MIP). With Carsten Lund
Carsten Lund
Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Florham Park, New Jersey, United States.Lund was born in Aarhus, Denmark, and received the...
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
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
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
László Babai
László Babai is a Hungarian professor of mathematics and computer science at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields...
and Carsten Lund, proved that MIP=NEXP. These algebraic techniques were expanded further by Fortnow, Babai, Leonid Levin
Leonid Levin
-External links:* at Boston University....
, and Mario Szegedy
Mario Szegedy
Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...
when they presented a new generic mechanism for checking computations.
Since this time Fortnow has continued to publish on a variety of topics in the field of computational complexity including derandomization, sparse language
Sparse language
In computational complexity theory, a sparse language is a formal language such that the number of strings of length n in the language is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes...
s, and oracle machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
s. Fortnow has also published on quantum computing, game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, genome sequencing, and economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...
.
Lance Fortnow's work in economics includes work in game theory, optimal strategies, and prediction. With Duke Whang, Fortnow has examined the classic game theory problem of the prisoner's dilemma
Prisoner's dilemma
The prisoner’s dilemma is a canonical example of a game, analyzed in game theory that shows why two individuals might not cooperate, even if it appears that it is in their best interest to do so. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950. Albert W...
, 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. Fortnow also examined the logarithmic
Logarithmic
Logarithmic can refer to:* Logarithm, a transcendental function in mathematics* Logarithmic scale, the use of the logarithmic function to describe measurements* Logarithmic growth* Logarithmic distribution, a discrete probability distribution...
market scoring rule (LMSR) with market makers. He helped to show that LMSR pricing is #P-hard and propose an appoximation technique for pricing permutation markets. He has also contributed to an examination the behavior of informed traders working with LMSR market makers.
Awards and honors
- 2007 ACM Fellow
- NSFNational Science FoundationThe National Science Foundation is a United States government agency that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National Institutes of Health...
Presidential Faculty Fellow from 1992–1998 - Fulbright Scholar to the Netherlands in 1996 and 1997