by Prasad Raghavendra (Simons Institute)

It has been 10 years since the Simons Institute was established, and what a decade it has been! We celebrated this milestone with a three-day symposium at Berkeley from May 25 through 27. 

A lot has happened in theory over the past decade. New research areas like privacy, algorithmic fairness, fine-grained complexity, and high-dimensional expanders have emerged. New problems that arose from machine learning and statistics have found their home in theory. Many old, long-standing peaks like near-linear time maximum flow and program obfuscation have been summited. In the theoretical realm, there have been numerous unexpected twists in the tale and unforeseen connections that have opened up beautiful vistas, like in the case of MIP*=RE or the work on log-concave polynomials. At the same time, seemingly “pure” theoretical ideas like the PCPs have surprisingly made their way into practice. Perhaps most importantly, the answer to the question “what is theoretical computer science?” has changed enormously over the past decade. 

The Simons Institute has been at the epicenter of many of these developments. While it is impossible for a conference to showcase all these developments, the amazing lineup of speakers at the 10th Anniversary Symposium gave us a glimpse. Moreover, they showed where some of the next grand challenges for theory may lie. All the talks from the conference are now viewable on the SimonsTV YouTube channel. I will briefly recall a few here.

• The conference kicked off with Jon Kleinberg’s talk on modeling conflict in social media. It wasn’t about the conflicts that have become endemic on social media, but about the internal conflict within ourselves as the users of social media. In particular, it is the conflict between the part of us that tells us what we want to do, and the part of us that tells us what we should do. Jon drove home the point with the example of eating chips (what we want) versus eating salad (what we should be doing). For a designer of social media, it is easy to cater to the short-term wants of users as expressed through their choices. This is akin to the host refilling the chip bowl every time it gets empty at a party. While this might drive user engagement in the short term, it runs the risk of losing users altogether in the longer term. Jon considered the question of how one could model this internal conflict and design systems that can cater to the “should” part of our internal selves. 
   
• Imagine a talk where the central object under consideration is a game between two players, say one on Earth and the other on the moon, who are answering questions to a referee. The same talk mentions Einstein, von Neumann, and Turing and weaves in foundations of quantum mechanics, operator algebras, the halting problem, and the PCP theorem for good measure, all within a single hour. You wouldn’t be alone if this does not feel like an actual talk, but just text that is auto-generated by one of the AI chatbots. Indeed, Thomas Vidick took us through this incredible journey between the worlds of physics, mathematics, and theoretical computer science. Just watch it if you haven’t already — here you go. 
   
• Tim Roughgarden spoke about blockchains, but it was really a master class on what a theorist brings to understanding a technology like blockchains. Tim cut through mountains of technicalities about blockchains and gave a succinct, yet comprehensive description of what blockchains essentially are. Paraphrasing Tim here, blockchains are a general-purpose public computer in the sky, with no owner or operator. While anyone can run programs on this computer in the sky, it supports user-owned data and verifies ownership on this data.
   
• Silvio Micali spoke about the consensus protocols that underlie the Algorand protocol. The problem of several parties agreeing on a bit in the presence of adversarial corruptions, known as Byzantine agreement, was all the rage in TCS more than three decades ago. It is precisely these theoretical ideas that are at the heart of the Algorand protocol. Silvio concluded that this is why practice needs theory and vice versa. We all agreed. 
   
• Rachel Lin gave a wonderful survey of indistinguishability obfuscation — a cryptographic primitive whose goal is to encrypt a program so as to hide everything but its functionality. She showed why indistinguishability obfuscation is one of the holy grails as far as cryptographic primitives go, and how it has transformed the landscape of cryptography in a very short time. 
   
• The symposium featured three talks on perhaps the grandest challenge of all, that of understanding how brains work. Bruno Olshausen and Ila Fiete spoke about the fascinating mechanisms that brains use to keep track of head directions, and how this neural circuitry seems to be similar across disparate species ranging from mammals to flies. Understanding these mechanisms started with experimental data, techniques from unsupervised learning to discern patterns, and finally ideas from coding theory to explain why. On the TCS end, Christos Papadimitriou spoke about their work on “algorithms” that underlie “neural assemblies” — an intermediate computational unit in the brain.

I have been to my fair share of workshops and conferences. Many workshops leave us with research questions to think about. Some leave us with a new technique or technical insight. There are a few conferences that we leave with a truly broader perspective on the field. The Simons Institute’s 10th Anniversary Symposium left us with all of these. But above all, it left us with a tremendous sense of optimism for what the next 10 years of theory will bring.