Lance Fortnow

Edit links
Source: Wikipedia, the free encyclopedia.
Lance Fortnow
BornAugust 15, 1963 (1963-08-15) (age 60)
NationalityAmerican
Alma mater
Georgia Tech
Northwestern University
University of Chicago
Doctoral advisorMichael Sipser
Doctoral studentsCarsten Lund
Websitehttp://lance.fortnow.com/
http://blog.computationalcomplexity.org/

Lance Jeremy Fortnow (born August 15, 1963) is a

interactive proof systems. As of January 2024, he was the Dean of the College of Computing at the Illinois Institute of Technology
.

Biography

Lance Fortnow received a doctorate in applied mathematics from

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.

Communications of the Association for Computing Machinery.[8]

Work

In his many publications, Fortnow has contributed important results to the field of

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

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

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

#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

  • 2007 ACM Fellow
  • NSF Presidential Faculty Fellow from 1992 to 1998
  • Fulbright Scholar
    to the Netherlands in 1996 and 1997
  • 2014 Nerode Prize

References

  1. ^ Lance Fortnow at the Mathematics Genealogy Project
  2. 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 ACM 39(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. 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

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Lance_Fortnow&oldid=1211538908"