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...
I hope all of you enjoyed a restorative summer. We are happy to be running in-person research programs again this fall — on Computational Complexity of Statistical Inference (CCSI), and on Geometric Methods in Optimization and Sampling (GMOS).
Yuansi Chen, an assistant professor at Duke University, made substantial progress last year toward proving the Kannan-Lovász-Simonovits (KLS) conjecture and, with it, the Bourgain slicing conjecture.
The Simons Institute's Breakthroughs series kicked off on June 16 with a talk by Virginia Vassilevska Williams of MIT, who recently developed the fastest method to date for multiplying two matrices, in collaboration with Josh Alman of Columbia.
This summer, the Simons Institute hosted our first indoor research activity in sixteen months, the 2021 Summer Cluster in Quantum Computation. In this episode of Polylogues, cluster organizer and Research Director for Quantum Computing Umesh Vazirani sits down with the other members of the organizing team to discuss some of the themes of the cluster: quantum complexity theory, quantum protocols and the nature of entanglement, quantum algorithms, and quantum chemistry.
The 13th Innovations in Theoretical Computer Science (ITCS) conference invites paper submissions through September 9.
This month, we are sharing once more our short documentary about computational complexity, which will open the Heidelberg Laureate Forum's mathematics and computer science film festival in November.
The Simons Institute is currently holding our first indoor research activity since the closure of the university due to the coronavirus in March 2020. The Summer Cluster in Quantum Computation is taking place at the Simons Institute from June 28 through August 6, 2021.
"Quantum computers aren’t the next generation of supercomputers — they’re something else entirely. Before we can even begin to talk about their potential applications, we need to understand the fundamental physics that drives the theory of quantum computing."
Our Spring 2021 programs on Satisfiability and on Theoretical Foundations of Computer Systems drew to a close earlier this month. It has been an unusual and challenging year in so many ways, brightened by the wide range of people around the world who have been able to participate in our workshops and lectures.
The world of cryptography saw a fundamental breakthrough this August, the beginning of an end for a very exciting period in the area of cryptography, one that began with the construction of candidate indistinguishability obfuscation schemes by Garg et. al. in 2013.