We’re delighted to share that Simons Institute Director Venkatesan Guruswami has been honored this summer with two 2026 Test of Time Awards for papers...
As of July 1, our friend and colleague Nikhil Srivastava is the Simons Institute’s Interim Associate Director. He succeeds Sampath Kannan, who returns...
First Proof has released the results of its second batch benchmark, assessing the ability of AI systems to autonomously solve naturally occurring...
In his presentation in the Complexity and Linear Algebra Boot Camp, Senior Scientist Nikhil Srivastava defines the problem of approximately diagonalizing a given dense matrix, and explains two phenomena that impede the convergence of diagonalization algorithms and complicate their analysis.
In this episode of Polylogues, Science Communicator in Residence Lakshmi Chandrasekaran sits down with two of the senior participants in our Summer 2025 Cryptography program, Yael Tauman Kalai (MIT) and Daniele Micciancio (UC San Diego).
This July, the Simons Institute co-hosted, in collaboration with Project CETI (Cetacean Translation Initiative) and Oceankind, the fourth annual workshop on Decoding Communication in Nonhuman Species. This series of workshops brings together researchers in machine learning, signal processing, data science, linguistics, robotics, and bioacoustics to explore the challenges and current state of the art in the study of nonhuman species communication.
In his contribution to the workshop on Decoding Communication in Nonhuman Species IV, Markus Freitag (Google) surveyed the rise of LLM-driven translation and its near-human performance in high-resource languages. He emphasized, however, that the “end of the language barrier” will require more than textual training data, especially for low-resource or nonhuman languages.
In this talk from the recent workshop on Decoding Communication in Nonhuman Species IV, Adam Kalai (OpenAI) explores how to evaluate machine translation systems in the absence of ground-truth reference translations, focusing on the extreme case where only acoustic outputs are available, without contextual or visual grounding.
On August 1, 2025, Simons Institute Science Communicator in Residence Lakshmi Chandrasekaran sat down with Moni Naor, one of the participants in this summer’s research program on cryptography, for a wide-ranging discussion of Naor’s path in the field, intersections of cryptography and complexity, the cryptographic technology behind CAPTCHA, and highlights of his own research.
Let me start with a confession. For many years, I was afraid of quantum and crypto. Quantum scared me because I didn’t know how to think about tensor products, and crypto because I couldn’t keep track of the quantifiers involved in interactive protocols. Yet, I can’t resist telling you about the compressed oracle method (and its generalization, the path-recording oracle), a beautiful linear algebraic technique that led to fundamental discoveries in quantum cryptography and complexity over the past year and a half, apparently right outside my office in Calvin Lab.
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.
Sum-of-squares spectral amplification (SOSSA) is a new method for compiling efficient block encodings that exploits the low energy of the initial state and relies on sum-of-squares optimization. This talk by Caltech graduate student Robbie King describes the ideas behind the new technique, and in particular how sum-of-squares optimization connects to Hamiltonian simulation and phase estimation.
SP1 Hypercube is a new multilinear-based proof system for proving the correctness of programs written in a high-level programming language. In his recent talk in the Summer 2025 Cryptography program workshop on Proofs, Ron Rothblum (Succinct) gave an overview of how such real-world proof systems work, while focusing on a key novel component in Hypercube: the jagged polynomial commitment scheme.