Lance Fortnow

  • Dean, College of Computing
  • Professor Computer Science

Tags:

  1. Home
  2. Office and Department Directory
  3. Directory
  4. Lance Fortnow

Education

Ph.D. in Applied Mathematics from Massachusetts Institute of Technology
B.A. in Mathematics, Computer Science from Cornell University

Research Interests

Awards

EATCS-IPEC Nerode Prize, 2014
ACM SIGACT Distinguished Service Award, 2014.
ACM Fellow, 2007
NSF Presidential Faculty Fellow, 1992–1998.
Fulbright Scholar in The Netherlands, 1996–1997.
Office of Naval Research Graduate Fellow, 1985–1988.
Kieval Prize for best graduating mathematics major at Cornell, 1985. Phi Beta Kappa and Phi Kappa Phi honor fraternities.

Publications

  1. Fortnow, L. and Santhanam, R. Robust simulations and significant separations. Information and Computation, 256(Supplement C):149 – 159, 2017.
  2. Chung, K. and Fortnow, L. Loopholes. The Economic Journal, 126(595):1774–1797, 2016.
  3. Batu, T., Fortnow, L., Rubinfeld, R., Smith, W. D., and White, P. Testing closeness of discrete distributions. Journal of the ACM, 60(1):4:1–4:25, February 2013.
  4. Fortnow, L., Lutz, J., and Mayordomo, E. Inseparability and strong hypotheses for disjoint NP pairs. Theory of Computing Systems, 51:229–247, 2012.
  5. Fortnow, L. and Grochow, J. Complexity classes of equivalence problems revisited. In-formation and Computation, 209(4):748–763, April 2011.
  6. Fortnow, L., Hitchcock, J., Pavan, A., Vinodchandran, N., and Wang, F. Extracting kolmogorov complexity with applications to dimension zero-one laws. Information and Computation, 209(4):627–636, April 2011.
  7. Fortnow, L. and Santhanam, R. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77(1):91–106, January 2011. Co-winner of the 2014 EATCS-IPEC Nerode Prize. JCSS Special issue celebrating Karp’s Kyoto Prize.
  8. Chen, Y., Dimitrov, S., Sami, R., Reeves, D., Pennock, D., Hanson, R., Fortnow, L., and Gonen, R. Gaming prediction markets: Equilibrium strategies with a market maker. Algorithmica, 58(4):930–969, December 2010.
  9. Buhrman, H., Fortnow, L., Koucký, M., Rogers, J., and Vereshchagin, N. Does the polynomial hierarchy collapse if onto functions are invertible? Theory of Computing Systems, 46(1):143–156, January 2010.
  10. Antunes, L. and Fortnow, L. Sophistication revisited. Theory of Computing Systems, 45(1):150–161, June 2009.
  11. Fortnow, L. and Klivans, A. Efficient learning algorithms yield circuit lower bounds. Journal of Computer and System Sciences, 75:27–36, January 2009. Special issue for selected papers from the 19th Annual Conference on Computational Learning Theory.
  12. Fortnow, L. A simple proof of Toda’s theorem. Theory of Computing, 5(7):135–140, 2009.
  13. Fortnow, L. and Vohra, R. The complexity of forecast testing. Econometrica, 77(1):93– 105, 2009.

Books

Fortnow, L. The Golden Ticket: P, NP and the search for the impossible. Princeton University Press, Princeton, 2013

Community Service

CRA Board, 2012-2015
Council of the CRA Computing Community Consortium, 2010-2013
ACM SIGACT, Chair 2009-2012, Vice-Chair 2005-2009.
Chair, Local Academic Advisory Committee, TTI-Chicago, 2006-2012. Executive Committee, DIMACS, 2000-2003.
Panel member for NSF and other funding agencies

Editorial Boards

ACM Transactions on Computation Theory (Founding Editor-in-Chief 2007-2010)

Journal of the ACM (2005-10)

Lecture Notes in Logic (2003-08)

Information and Computation (2001-2009)

Scientific Board, Electronic Colloquium on Computational Complexity, 2005-2008

The Chicago Journal of Theoretical Computer Science
Computational Complexity Column in Bulletin of the European Association for Theoretical Computer Science, 2000-2004

Available for media interviews on the following topics:

For media inquiries, please contact

Petra Kelly
Communications Director
773.771.1064

Media Appearances

College of Computing Dean Lance Fortnow: Computation Is All Around Us, and You Can See It if You Try

Quanta Magazine

Once you start thinking about computation, you start to see it everywhere. Take mailing a letter through the postal service. Put the letter in an envelope with an address and a stamp on it, and stick it in a mailbox, and somehow it will end up in the recipient’s mailbox. That is a computational process — a series of operations that move the letter from one place to another until it reaches its final destination. This routing process is not unlike what happens with electronic mail or any other piece of data sent through the internet. Seeing the world in this way may seem odd, but as Friedrich Nietzsche is reputed to have said, “Those who were seen dancing were thought to be insane by those who could not hear the music.”

College of Computing Dean Lance Fortnow Comments on Efficient New Way to Count

Quanta Magazine

Imagine that you’re sent to a pristine rainforest to carry out a wildlife census. Every time you see an animal, you snap a photo. Your digital camera will track the total number of shots, but you’re only interested in the number of unique animals — all the ones that you haven’t counted already. What’s the best way to get that number? “The obvious solution requires remembering every animal you’ve seen so far and comparing each new animal to the list,” said Lance Fortnow, a computer scientist at the Illinois Institute of Technology. But there are cleverer ways to proceed, he added, because if you have thousands of entries, the obvious approach is far from easy.