Simons Institute for the Theory of Computing, UC Berkeley

Ramon van Handel surveys recent progress on constructing graphs, manifolds and groups with optimal spectral gaps, which control how rapidly random walks explore a structure. The talk describes a polynomial method that proves optimality in new settings and connects these developments to longstanding questions about the prevalence of optimal gaps.

Ryan O’Donnell presents simple explicit families of expander graphs whose analysis needs only a small amount of group theory. The lecture explains their expansion properties and shows how these constructions can lead to stronger objects, including super-expanders and non-sofic groups with property (T).

Sanjam Garg explores encryption whose decryption condition is solving a puzzle or proving a mathematical statement, rather than simply possessing a conventional cryptographic key. The lecture traces the development of this idea and describes recent advances that are making such schemes more practical for real applications.

Brendan McMahan examines how AI systems can learn from high-quality information that is distributed and privacy-sensitive. He introduces principles for precise discussions of privacy and AI, then connects them to the theory and practical methods needed in real applications, including work on decentralised and privacy-preserving learning.

Rui-Jie Yew and Greg Demirchyan discuss two alignment problems in AI governance. Limited understanding of models makes safety risks and the faithfulness of audits difficult to establish, complicating regulation. At the same time, technologies presented as safety measures can reshape oversight in ways that conflict with regulatory aims. The speakers consider adaptable governance and practical steps towards effective oversight.

Katrina Ligett explores why learning theory can make pessimistic predictions even when practical systems succeed. Instead of analysing only worst-case algorithms and data, she proposes reformulating questions around properties that explain algorithmic success and instance-specific performance. Examples in generalisation and privacy illustrate how these perspectives could narrow the gap between theory and empirical practice and create new mathematical questions.

Jon Kleinberg examines how AI world models differ from human models and how these differences affect joint decision-making. Examples from chess, navigation and generative systems show that competence alone may fail to support a weaker human partner or accommodate unexpected changes. The talk also considers theoretical cases where successful generation does not imply that an agent can identify the model generating its observations.

Virginia Vassilevska Williams surveys the search for faster matrix multiplication, from Strassen’s first improvement over cubic time to modern bounds. The talk explains the role of this basic operation in graph algorithms, numerical linear algebra and learning, and the unresolved question of whether its exponent can reach the quadratic output-size lower bound. It offers intuition for the development and possible future direction of the area.

Robert Tarjan asks how much data-structure operations can be accelerated using multiple unsynchronised processes. The presentation examines the challenges of exploiting concurrency through joint work with Siddhartha Jayanti on efficient concurrent disjoint-set union. It includes recent approaches that remove the need for randomisation.

Yoshua Bengio discusses risks arising when general-purpose AI agents autonomously pursue goals, including misuse, deception and loss of human control. He presents Scientist AI as a proposed non-agentic alternative combining a model that explains observations with question-answering inference. Explicit uncertainty is central to its design, with potential applications in scientific research and assessing other AI systems.

Sasha Rush surveys research on increasing language-model capability through computation at inference time. The lecture places test-time scaling alongside parameter and data scaling, examines model self-improvement and discusses implications for the design of reasoning models and open-source research efforts.

Jordan Ellenberg explores how machine learning might contribute to mathematical discovery. Drawing on collaborative work with DeepMind on a combinatorics problem, he considers the distinction between obeying formal rules and producing ideas that mathematicians judge important or ingenious, and discusses near-term changes to mathematical practice.

Rocco Servedio surveys algorithms that determine whether very large objects possess a property, or are far from having it, by examining only a small part. The lecture covers progress on classic problems and newer testing frameworks motivated by machine-learning theory and high-dimensional data analysis.

Noga Ron-Zewi examines randomised algorithms that make decisions after inspecting only a small fraction of their input. The lecture traces connections between local error detection and correction, computational hardness and privacy-related applications, then discusses unresolved challenges in constructing local algorithms for error-correcting codes.

Leonardo de Moura explains how the Lean proof assistant supports interactive mathematical proofs and mechanically verified software. The lecture discusses extensibility, collaborative formalisation and Lean’s mathematical library, with examples from the Liquid Tensor Experiment, mathematics education and the verification challenges associated with AI-generated proofs.

Vijay V. Vazirani presents a two-part account of the Micali–Vazirani algorithm for maximum-cardinality matching. The first part develops background from bipartite matching and Edmonds’ algorithm, explains why shortest augmenting paths create difficulties, and introduces double depth-first search. The second develops a structural theory of alternating paths and blossoms that supports the algorithm and its recently completed proof.

Floris Geerts analyses the expressive power of graph-learning methods. Predictions on graph-structured data must respect isomorphism, motivating invariant operations such as neighbourhood aggregation. The lecture connects these compositional operations with database theory to explain what different graph-learning architectures can represent, with applications including molecules, social networks and recommendation systems.

Monika Henzinger surveys algorithms that maintain graph information as vertices and edges change. The lecture explains major algorithmic techniques and open problems, and shows how dynamic data structures support applications such as clustering and recent breakthroughs in static maximum-flow and minimum-cost-flow algorithms.

Aaron Sidford introduces recent advances towards nearly linear-time algorithms for fundamental computational problems. Examples include matching, maximum flow, minimum cuts, linear systems and linear programming. The lecture explains how continuous optimisation, dynamic data structures and sketching interact, often transferring techniques between apparently different settings.