Lance Fortnow Contents Biography Work Awards and honors References External links Navigation menuLance...
ImpagliazzoBodlaenderFellowsFortnowDemaineFominHajiaghayi
Living peopleTheoretical computer scientistsMassachusetts Institute of Technology alumniGeorgia Institute of Technology faculty1963 birthsFulbright ScholarsFellows of the Association for Computing MachineryScience bloggers
computer scientistcomputational complexityinteractive proof systemsSchool of Computer ScienceGeorgia TechMichael SipserUniversity of ChicagoNorthwestern UniversityGeorgia Institute of TechnologySchool of Computer ScienceWilliam Gasarchcomputational complexityprotocolspolynomial hierarchyNoam NisanCarsten LundAdi ShamirLászló BabaiLeonid LevinMario Szegedyderandomizationsparse languagesoracle machinesquantum computinggame theorygenome sequencingeconomicsprisoner's dilemmalogarithmicmarket makers#P-hard
Lance Fortnow | |
|---|---|
| Born | August 15, 1963 (1963-08-15) (age 55) |
| Nationality | American |
| 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 | 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 currently chairs the School of Computer Science at Georgia Tech.
Contents
1 Biography
2 Work
3 Awards and honors
4 References
5 External links
Biography
Lance Fortnow received a doctorate in Applied Mathematics from MIT in 1989,[1] 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.[2][3]
Fortnow was the founding editor-in-chief of the journal ACM Transactions on Computation Theory.[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 2003, Fortnow 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 the Communications of the Association of Computing Machinery.[8][9]
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.[10] 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.[11]
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.[12] Their work was hardly two weeks old when Adi Shamir employed it to prove that IP=PSPACE.[13] 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.[14] These algebraic techniques were expanded further by Fortnow, Babai, Leonid Levin, and Mario Szegedy when they presented a new generic mechanism for checking computations.[15]
Since this time 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.
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.[16] 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 approximation technique for pricing permutation markets.[17] He has also contributed to an examination the behavior of informed traders working with LMSR market makers.[18]
Fortnow has also authored a popular science book, titled The Golden Ticket: P, NP and the Search for the Impossible.[19], which was loosely based on an article he previously wrote for CACM in 2009.[20] 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.[21]
Awards and honors
- 2007 ACM Fellow
NSF Presidential Faculty Fellow from 1992–1998
Fulbright Scholar to the Netherlands in 1996 and 1997- 2014 Nerode Prize
References
^ Lance Fortnow at the Mathematics Genealogy Project
^ "College of Computing Hires Fortnow, Anton to Lead Schools" (Press release). Georgia Tech College of Computing. March 19, 2012. Retrieved October 4, 2012..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ Northwestern University Electrical Engineering and Computer Science Department Faculty
^ ACM Transactions on Computation Theory
^ ACM SIGACT
^ IEEE Conference on Computational Complexity
^ Computational Complexity Weblog
^ J. Markoff. Prizes Aside, the P-NP Puzzler Has Consequences. The New York Times 7 Oct. 2009.
^ L. Fortnow. The Status of the P Versus NP Problem. Communications of the ACM 9 (2009).
^ 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.
^ L. Fortnow and M. Sipser. Are there interactive protocols for co-NP languages? Information Processing Letters, 28:249-251, 1988.
^ C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992.
^ A. Shamir. IP = PSPACE. Journal of the ACM 39(4):869-877, 1992.
^ L. Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1(1):3-40, 1991.
^ 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.
^ 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.
^ 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.
^ 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.
^ Fortnow, Lance. The Golden Ticket: P, NP and the Search for the Impossible. Princeton University Press, 2013
^ Fortnow, Lance. The Status of the P Versus NP Problem. Communications of the ACM, 52(9): 78-86. September 2009. Review Article
^ P vs NP. Data Skeptic, 2017
External links
- Fortnow's Homepage
- List of Publications
Authority control  |
|
|---|
