Seminar Details

We live in a new age of computing, driven by faster distributed computation, strong optimization, data-driven algorithms, and of course dramatic advances in artificial intelligence. We’ve made dramatic progress on problems thought unsolvable a decade ago.What does this brave new world tell us about computational complexity? The P vs NP problem transforms from a barrier telling us what we cannot do to a guide to what’s possible. We are heading towards a surprising utopian computing world where we can solve many difficult problems quickly in practice while all our cryptographic protocols remain secure, and where we can make significant progress in learning in nearly every domain.We’ll 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. We search for not only answers, but the right questions to help us chart the future of both fields.

Bio

Lance Fortnow is the inaugural Dean of the College of Computing at the Illinois Institute of Technology. At DIMACS, Fortnow represented the NEC Research Institute on the executive committee from 2000-2003 and co-chaired the 2004-2008 Special Focus on Computation and the Socio-Economic Sciences. He has authored the Computational Complexity blog since 2002 and wrote the popular science book The Golden Ticket: P, NP, and the Search for the Impossible.