Keynote Speakers

STOC 2022 will have six keynote speakers:

At the Accademia Lincei event:

Giorgio Parisi

Accademia Nazionale dei Lincei and Sapienza University of Rome

"Spin Glass Theory"

Abstract: In this talk I will present some results on the Sherrington Kirkpatrick model, that is the simplest spin glass model. I will try to present both a heuristic approach based on the cavity approach and some rigorous results, sketching the tools used to obtain the proofs.

Andrea Montanari

Stanford University

"Algorithmic Spin Glass Theory"

Abstract: Mean field spin glasses are random functions typically defined over the sphere or the discrete hypercube in N dimensions. Giorgio Parisi received the 2021 Nobel Prize in Physics for developing a set of powerful theoretical ideas (most notably, replica symmetry breaking) that allowed to explore the structure of these random functions in high dimension.

Over the last 35 years, tools from spin glass theory have been adapted to study a variety of random optimization and learning problems. However, a rigorous understanding of the algorithmic implications of replica symmetry breaking has emerged only recently. I will discuss recent results in this direction focusing on the problems of optimizing spin glass Hamiltonians and sampling from the associated Gibbs measure.

[Based on joint work with Ahmed El Alaoui and Mark Sellke]

Silvio Micali

MIT and Algorand

"We, The People, Agree"

Patrick Hayden

Stanford University

"Navigating in a maelstrom: complexity and the structure of spacetime"

Abstract: Understanding how general relativity and quantum mechanics coexist remains a profound scientific mystery. Prof. Hayden considers the interface of quantum information and quantum gravity and the possibility that quantum complexity theory plays an unlikely role.

Umesh Vazirani

University of California, Berkeley

"Testing quantum computers and quantum mechanics"

Abstract: Quantum computation forces us to reimagine our conception of computation, with major implications for both computer science and physics. Prof. Vazirani will address philosophical questions such as "is quantum physics falsifiable?" and practical questions such as "how can we test and benchmark quantum computers?" and argue that these are two sides of the same coin.

On Friday June 24:

Claire Mathieu

CNRS, Paris

"Pandemic Models"

Abstract: Covid is transmitted from person to person by aerosols. How do we represent population contacts? How do we model the diffusion of the epidemics among the population? How do we model the effect of changes in the virus, in vaccinations, and in public health measures? How predictable is the result? How do we track transmissions? How do we make measures acceptable?

In this talk, I will present work done on actual contact graphs as well as on artificial contact models, present the challenges and try to suggest directions in which computer scientists may have expertise to contribute fruitfully to this field of research.