Letter from the Director, September 2025

Dear friends,

Greetings from Berkeley, where after a very busy summer of crypto and quantum fun, we’ve just kicked off our Fall 2025 programs on Complexity and Linear Algebra, and on Algorithmic Foundations for Emerging Computing Technologies.

We all learn how to solve linear equations, multiply matrices, and, if we’re lucky, compute eigenvalues and eigenvectors. The Complexity and Linear Algebra program is about understanding how efficiently we can hope to do these things, which remains quite mysterious. But understanding and efficiency mean very different things in applied math, pure math, theoretical computer science, and high-performance computing. This program collects people from these complementary and sometimes conflicting perspectives, with the hope of new discoveries and a lasting understanding among them.

The program on Algorithmic Foundations for Emerging Computing Technologies is a new direction for the Simons Institute, in which emerging hardware trends are taken as a springboard for theoretical exploration. The goal of the program is to define new computational models that are responsive to changing hardware technologies, and to analyze algorithms and lower bounds in these models. Some of the memory in today’s processors can be accessed at almost the same speed that basic computational operations take. (Some) memory is organized to have parallel connections to the cache, and hence greater reading and writing from this memory can be done at much greater bandwidth. Some computation can be performed within memory, opening the door for new kinds of parallelism. This program will explore these and other trends in emerging hardware and seek to model them realistically.

It is rare for models of computation to be defined in reaction to technological trends and realities. Theory has typically led the way, anticipating broad trends and defining models (such as the Turing machine, the RAM model, the PRAM model, the quantum computing model, the streaming model, etc.), and real technologies have fit well enough to make these models useful. The challenge here will be to model technological trends closely enough to make the models useful, but not so closely that they become rapidly obsolete.

This month, Simons Institute senior scientist and indispensable member of our Fun Committee Nikhil Srivastava shares the latest installment in his periodic column, Theory at the Institute and Beyond. Nikhil leads us on a deep dive into the compressed oracle method, a technique that has grown to fruition through the work of participants in our Quantum Pod, with important implications for both quantum computing and cryptography. 

At the end of July, the Institute co-hosted the fourth annual workshop on Decoding Communication in Nonhuman Species, in collaboration with Project CETI and Oceankind. You can learn more about this exciting workshop series here. And we’re highlighting a couple of our favorite talks in this issue of the newsletter: Markus Freitag on Machine Translation of Human Languages in the Age of LLMs, and Adam Kalai on Validation by Listening. 

Also in our SimonsTV corner this month, we have the latest installment in our Polylogues web series, this time featuring an interview with Cryptography 2025 participant Moni Naor.

In closing, I’d like to congratulate our friend and colleague Peter Bartlett, Machine Learning Pod director and former associate director of the Simons Institute, for the extraordinary honor of being selected as one of the plenary speakers at the 2026 International Congress of Mathematicians.

Hope to see you in Berkeley soon!
Venkat

Venkatesan Guruswami
Interim Director, Simons Institute for the Theory of Computing