In this month’s newsletter, we’re highlighting a 2015 talk by Chris Umans on some of the then state-of-the-art approaches to bound the matrix...
Greetings from Berkeley! We are gearing up for a busy wrap-up of the spring semester, with five back-to-back workshop weeks at the Simons Institute...
Ten years ago, researchers proved that adding full memory can theoretically aid computation. They’re just now beginning to understand the implications...
For decades, mathematicians have been inching forward on a problem about which sets contain evenly spaced patterns of three numbers. Last month, two computer scientists blew past all of those results.
Cryptographers have shown how perfect security can undermine machine learning models.
In his Theoretically Speaking public lecture this month, Pixar co-founder Alvy Ray Smith shared his voyage from an early career as a theoretical computer scientist to pioneering the digital graphics revolution.
Greetings from Berkeley, where February is a mixture of glorious spring blossoms and surprise snow flurries.
What is the computational complexity of computational complexity? In his Richard M. Karp Distinguished Lecture, Eric Allender (Rutgers University) explored the core themes of the Spring 2023 research program on Meta-Complexity.
In 2021, the Simons Institute hosted a workshop titled 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing. One of the talks was by Simons Institute Founding Director Richard Karp, who gave a firsthand account of early developments in computational complexity theory.
This semester at the Simons Institute, the Meta-Complexity program is buzzing along with intense activity in the form of multiple reading groups and a weekly seminar, on top of the usual three workshops and boot camp.
Rafael Pass (Cornell Tech and Tel Aviv University) gave a two-part tutorial presentation on Cryptography and Kolmogorov Complexity, at the Simons Institute's Meta-Complexity Boot Camp.
Greetings from Berkeley. I hope 2023 is off to a great start for you. To kick off the new year, we’ve relaunched our Simons Institute website with an updated look and feel.
Rahul Ilango (MIT) gave a two-part tutorial presentation on the Quest for Hardness of Meta-Complexity: Progress, Barriers, and Next Steps, at the Simons Institute's Meta-Complexity Boot Camp.