Data-Intensive Distributed Systems LaboratoryCS Seminar
Date: April 15th, 2026
Time: 12:50pm
Room: SB111
Lance Fortnow
Professor
Computer Science Department
Illinois Institute of Technology
Talk Title
Complexity in the Era of AI and Data-Driven Computing
Talk Abstract
In 2013 I wrote a book chapter on an imagined world where P = NP. A world with advances in medicine, translation, video recognition and generation, and much more. With the advances we have seen in computing power, optimization, data-driven algorithms, and of course remarkable advances in artificial intelligence, much of this world is coming true. We have made dramatic progress on problems thought unsolvable a decade ago. With one major exception, our cryptographic protocols have remained secure.
How did we get to this seemingly impossible world I call Optiland where we can solve many difficult problems quickly in practice while our secrets remain secure, and what does it mean for our understanding and role of computational complexity?
We will give a (mostly) non-technical overview that takes a step back and rethinks complexity in light of these advances, what AI tells us about complexity, and what complexity tells us about AI.
Speaker Bio
Lance Fortnow is a professor in Computer Science at the Illinois Institute of Technology and a visiting fellow at Magdalen College, Oxford for Hilary Term 2026. He was the founding dean of the College of Computing at Illinois Tech, serving from June 2019 to June 2025.
Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before joining Illinois Tech, he was chair of the School of Computer Science at the Georgia Institute of Technology and previously a professor at Northwestern University and the University of Chicago, a senior research scientist at the NEC Research Institute, and a one-year visitor at CWI and the University of Amsterdam. He also held an adjunct professorship at the Toyota Technological Institute at Chicago from 2007 to 2018.
Fortnow's research spans computational complexity and its applications. His work on interactive proof systems and time-space lower bounds for satisfiability has led to his election as a 2007 ACM Fellow. In addition, he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97. His current research focuses on how artificial intelligence changes the way we think about both the theory and applications of computing.
Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transactions on Computation Theory, as chair of ACM SIGACT, and on the Computing Research Association board of directors. He chaired the IEEE Conference on Computational Complexity from 2000 to 2006. Fortnow founded and co-authors the Computational Complexity weblog, the first major theoretical computer science blog, which has run continuously since 2002.
Fortnow's survey The Status of the P versus NP Problem is one of the CACM's most downloaded articles. He wrote a popular science book, The Golden Ticket: P, NP and the Search for the Impossible, loosely based on that article.