Lance Fortnow

  • Dean, College of Computing
  • Professor Computer Science

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