Lance Fortnow
   HOME

TheInfoList



OR:

Lance Jeremy Fortnow (born August 15, 1963) is a
computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
known for major results in
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
and interactive proof systems. Since 2019, he has been at the
Illinois Institute of Technology The Illinois Institute of Technology, commonly referred to as Illinois Tech and IIT, is a Private university, private research university in Chicago, Illinois, United States. Tracing its history to 1890, the present name was adopted upon the m ...
, where he is currently the Dean of the College of Computing.


Biography

Lance Fortnow received a doctorate in applied mathematics from
MIT The Massachusetts Institute of Technology (MIT) is a private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of modern technology and sc ...
in 1989, supervised by
Michael Sipser Michael Fredric Sipser (born September 17, 1954) 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 Massa ...
. Since graduation, he has been on the faculty of the
University of Chicago The University of Chicago (UChicago, Chicago, or UChi) is a Private university, private research university in Chicago, Illinois, United States. Its main campus is in the Hyde Park, Chicago, Hyde Park neighborhood on Chicago's South Side, Chic ...
(1989–1999, 2003–2007),
Northwestern University Northwestern University (NU) is a Private university, private research university in Evanston, Illinois, United States. Established in 1851 to serve the historic Northwest Territory, it is the oldest University charter, chartered university in ...
(2008–2012) and the
Georgia Institute of Technology The Georgia Institute of Technology (commonly referred to as Georgia Tech, GT, and simply Tech or the Institute) is a public university, public research university and Institute of technology (United States), institute of technology in Atlanta, ...
(2012–2019) as chair of the School of Computer Science. From 1999-2003 he was a Senior Research Scientist at the NEC Research Institute. Fortnow was the founding editor-in-chief of the journal ''ACM Transactions on Computation Theory'' in 2009. He was the chair of
ACM SIGACT ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publi ...
and succeeded by Paul Beame. He was the chair of the IEEE Conference on Computational Complexity from 2000 to 2006. In 2002, he began one of the first blogs devoted to
theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...
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 The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...
in '' Communications of the Association for Computing Machinery''.


Work

In his many publications, Fortnow has contributed important results to the field of
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
. While still a graduate student at MIT, Fortnow showed that there are no perfect zero-knowledge
protocols Protocol may refer to: Sociology and politics * Protocol (politics), a formal agreement between nation states * Protocol (diplomacy), the etiquette of diplomacy and affairs of state * Etiquette, a code of personal behavior Science and technology ...
for
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
languages unless the
polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...
collapses. With Michael Sipser, he also demonstrated that relative to a specific
oracle An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...
there exists a language in
co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...
that does not have an interactive protocol. In November 1989, Fortnow received an email from
Noam Nisan Noam Nisan (; born June 20, 1961) is an Israeli computer scientist and professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory. Biography Ni ...
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 Adi Shamir (; born July 6, 1952) is an Israeli cryptographer and inventor. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identification sc ...
employed it to prove that IP=
PSPACE 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. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...
. 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ó "Laci" Babai (born July 20, 1950, in Budapest) a fellow of the American Academy of Arts and Sciences, and won the Knuth Prize. Babai was an invited speaker at the International Congresses of Mathematicians in Kyoto (1990), Zürich (199 ...
and Carsten Lund, proved that MIP= NEXP. These algebraic techniques were expanded further by Fortnow, Babai,
Leonid Levin Leonid Anatolievich Levin ( ; ; ; born November 2, 1948) is a Soviet-American mathematician and computer scientist. He is known for his work in randomness in computing, algorithmic complexity and intractability, average-case complexity, fou ...
and Mario Szegedy when they presented a new generic mechanism for checking computations. Fortnow has continued to publish on a variety of topics in the field of computational complexity including
derandomization A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
,
sparse language In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length ''n'' in the language, is bounded by a polynomial function of ''n''. They are ...
s, and
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 black box, called an oracle, which is able to solve certain problems in a single operation. The ...
s. Fortnow has also published on
quantum computing A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of wave-particle duality, both particles and waves, and quantum computing takes advantage of this behavior using s ...
,
game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
,
genome sequencing Whole genome sequencing (WGS), also known as full genome sequencing or just genome sequencing, is the process of determining the entirety of the DNA sequence of an organism's genome at a single time. This entails sequencing all of an organism's ...
and
economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and interac ...
. 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 The prisoner's dilemma is a game theory thought experiment involving two rational agents, each of whom can either cooperate for mutual benefit or betray their partner ("defect") for individual gain. The dilemma arises from the fact that while def ...
, 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 A market maker or liquidity provider is a company or an individual that quotes both a buy and a sell price in a tradable asset held in inventory, hoping to make a profit on the difference, which is called the '' bid–ask spread'' or ''turn.'' Th ...
. He helped to show that LMSR pricing is #P-hard and proposed an approximation technique for pricing permutation markets. He has also contributed to a study of the behavior of informed traders working with LMSR market makers. Fortnow has also written a science book, ''The Golden Ticket: P, NP and the Search for the Impossible'', which was loosely based on an article he had written 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''."P vs NP"
''Data Skeptic'', 2017


Awards and honors

* 2007
ACM Fellow ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals ...
*
NSF NSF may stand for: Political organizations *National Socialist Front, a Swedish National Socialist party *NS-Frauenschaft, the women's wing of the former German Nazi party * National Students Federation, a leftist Pakistani students' political g ...
Presidential Faculty Fellow from 1992 to 1998 *
Fulbright Scholar The Fulbright Program, including the Fulbright–Hays Program, is one of several United States cultural exchange programs with the goal of improving intercultural relations, cultural diplomacy, and intercultural competence between the peopl ...
to the Netherlands in 1996 and 1997 * 2014
Nerode Prize The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of parameterized complexity, multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science an ...


References


External links


Fortnow's home page

List of publications
{{DEFAULTSORT:Fortnow, Lance Living people Theoretical computer scientists Massachusetts Institute of Technology School of Science alumni Georgia Tech faculty 1963 births 2007 fellows of the Association for Computing Machinery Science bloggers 21st-century science writers