Abstract

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.

https://www.cs.rutgers.edu/news-events/cs-events/icalrepeat.detail/2025/05/12/4840/-/complexity-in-the-era-of-ai-and-data-driven-computing

See: https://theory.cs.rutgers.edu/theory_seminar