CMSA

Fault-tolerant quantum computation via topological order on fractals and emergent symmetries
2023-04-14 10:00 - 11:30 (America/New_York) | Hybrid – G10
Quantum Matter Seminar
Speaker: Guanyu Zhu (IBM Quantum, T. J. Watson Research Center)
Title: Fault-tolerant quantum computation via topological order on fractals and emergent symmetries
Abstract: Topological quantum error correcting codes in integer spatial dimensions have been widely studied in the field of quantum information. A remaining major challenge is to reduce the space-time overhead for universal fault-tolerant quantum computation with topological codes. In the first part of my talk, I will present a theory of topological order and quantum codes on fractals embedded in three and higher dimensions and its connection to systolic geometry. The construction of such fractal codes can hence significantly reduce the space overhead. In the second part, I will show how to perform fault-tolerant non-Clifford logical gates in such fractal codes using the idea of emergent symmetries. In particular, I will discuss the existence of higher-form symmetries corresponding to sweeping of certain codimension-2 invertible defects and exotic gapped boundaries which condense such defects.
References:
1. PRX Quantum 3 (3), 030338 (2022), Guanyu Zhu, Tomas Jochym-O’Connor, Arpit Dua
2. arXiv:2201.03568 (2022), Arpit Dua, Tomas Jochym-O'Connor, Guanyu Zhu
3. arXiv:2208.07367 (2022), Maissam Barkeshli, Yu-An Chen, Sheng-Jie Huang, Ryohei Kobayashi, Nathanan Tantivasadakarn, Guanyu Zhu

Recent progress on coupled Einstein-Yang-Mills dynamics
2023-04-18 12:00 - 13:00 | Common Room, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Member Seminar
Speaker: Puskar Mondal
Title: Recent progress on coupled Einstein-Yang-Mills dynamics
Abstract: I will discuss my recent work with prof. S.T. Yau on Einstein-Yang-Mills theory. I’ll discuss the main ideas behind the stability of the Minkowski and Milne space time under coupled gauge-gravity perturbations. Construction of the gauge invariant energies that control the suitable norms of the physical degrees of freedom in a double-null framework play an important role. I’ll sketch how the special structure of the Einstein and Yang-Mills nonlinearities play a crucial role in obtaining the stability result of non-expanding spacetimes in particular AF spacetimes.

Diagonalizing Transition Matrices of Card Shuffles
2023-04-19 15:30 - 16:30 | Science Center 232, Harvard Science Center, 1 Oxford Street, Cambridge MA 02138
Probability Seminar
Speaker: Evita Nestoridi (Stonybrook)

Title: Diagonalizing Transition Matrices of Card Shuffles
Abstract: In their seminal work, Diaconis and Shahshahani used representation theory of the symmetric group to diagonalize the transition matrix of random transpositions. More recently, Dieker and Saliola introduced another technique to diagonalize the random-to-random card shuffle. In this talk we will discuss connections between these techniques as well as application to card shuffling.

Black hole collider physics
2023-04-20 13:30 - 14:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Speaker: Julio Parra Martinez, Caltech
Title: Black hole collider physics
Abstract: Despite more than a century since the development of Einstein’s theory, the general relativistic two-body problem remains unsolved. A precise description of its solution is now essential, as it is necessary for understanding the strong-gravity dynamics of compact binaries observed at LIGO/VIRGO/KAGRA and in future gravitational wave observatories. In this talk, I will describe how considering the scattering of black holes and gravitons can shed new light on this problem. I will explain how using modern ideas from collider and particle physics we can calculate scattering observables in classical gravity, and extract the basic ingredients that describe the bound binary dynamics. Such calculations have produced state-of-art predictions for current and future gravitational wave observatories, which open the door for further discovery as we enter this new era of precision gravitational physics.

A model of the cuprates: from the pseudogap metal to d-wave superconductivity and charge order
2023-04-21 10:00 - 11:30 | Hybrid – G10
Quantum Matter Seminar
Speaker: Prof. Subir Sachdev (Harvard)
Title: A model of the cuprates: from the pseudogap metal to d-wave superconductivity and charge order
Abstract: Soon after the discovery of high-temperature superconductivity in the cuprates, Anderson proposed a connection to quantum spin liquids. But observations since then have shown that the low-temperature phase diagram is dominated by conventional states, with a competition between superconductivity and charge-ordered states which break translational symmetry. We employ the “pseudogap metal” phase, found at intermediate temperatures and low hole doping, as the parent to the phases found at lower temperatures. The pseudogap metal is described as a fractionalized phase of a single-band model, with small pocket Fermi surfaces of electron-like quasiparticles whose enclosed area is not equal to the free electron value, and an underlying pi-flux spin liquid with an emergent SU(2) gauge field. This pi-flux spin liquid is now known to be unstable to confinement at sufficiently low energies. We develop a theory of the different routes to confinement of the pi-flux spin liquid and show that d-wave superconductivity, antiferromagnetism, and charge order are natural outcomes. We argue that this theory provides routes to resolving a number of open puzzles on the cuprate phase diagram.
As a side result, at half-filling, we propose a deconfined quantum critical point between an antiferromagnet and a d-wave superconductor described by a conformal gauge theory of 2 flavors of massless Dirac fermions and 2 flavors of complex scalars coupled as fundamentals to a SU(2) gauge field.
This talk is based on Maine Christos, Zhu-Xi Luo, Henry Shackleton, Mathias S. Scheurer, and S. S., arXiv:2302.07885

The Tameness of Quantum Field Theories
2023-04-24 11:00 - 12:00 | Jefferson 368
Swampland Seminar
Speaker: Thomas Grimm (Utrecht U.)

Title: The Tameness of Quantum Field Theories
Abstract: Tameness is a generalized notion of finiteness that is restricting the geometric complexity of sets and functions. The underlying mathematical foundation lies in tame geometry, which is built from o-minimal structures introduced in mathematical logic. In this talk I formalize the connection between quantum field theories and logical structures and argue that the tameness of a quantum field theory relies on its UV definition. I quantify our expectations on the tameness of effective theories that can be coupled to quantum gravity and on CFTs. In particular, I present tameness conjectures about CFT observables and propose universal constraints that render spaces of CFTs to be tame sets. I then highlight the relation of these conjectures to other swampland conjectures, e.g., by arguing that the tameness of CFT observables restricts having parametrical gaps in the operator spectrum.

Recent advances in scalar curvature and positive mass theorems
2023-04-24 13:30 - 14:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
General Relativity Seminar
Speaker: Tin Yau Tsang, University of California Irvine
Title: Recent advances in scalar curvature and positive mass theorems

Abstract: First, we have a review of classical tools for studying scalar curvature and positive mass theorem. Then we are going to discuss some advances and new perspectives on these tools which lead to a deeper understanding of geometry and initial data sets.

On complete Calabi-Yau metrics and some related Monge-Ampere equations
2023-04-25 12:00 - 13:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Member Seminar
Speaker: Freid Tong
Title: On complete Calabi-Yau metrics and some related Monge-Ampere equations
Abstract: We will give a basic introduction to constructions for complete Calabi-Yau metrics. A systematic approach to construct such metrics using PDE methods was proposed in the work of Tian-Yau in the 90s and have attracted a lot of attention in recent years. I will discuss some joint work with B. Guo and T. Collins on a singular version of such a construction, as well as some ongoing work with Prof. Yau on some related boundary value problems.

Boundary behavior at classical and quantum phase transitions
2023-04-26 12:30 - 13:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Speaker: Max Metlitski (MIT)
Title: Boundary behavior at classical and quantum phase transitions
Abstract: There has been a lot of recent interest in the boundary behavior of materials. This interest is driven in part by the field of topological states of quantum matter, where exotic protected boundary states are ubiquitous. In this talk, I’ll ask: what happens at a boundary of a system, when the bulk goes through a phase transition. While this question was studied in the context of classical statistical mechanics in the 70s and 80s, basic aspects of the boundary phase diagram for the simplest classical phase transitions have been missed until recently. I’ll describe progress in this field, as well as some extensions to quantum phase transitions.

Toolformer: Language Models Can Teach Themselves to Use Tools
2023-04-26 14:00 - 15:00 | Virtual
New Technologies in Mathematics Seminar
Speaker: Timo Schick, Meta AI
Title: Toolformer: Language Models Can Teach Themselves to Use Tools
Abstract: Language models exhibit remarkable abilities to solve new tasks from just a few examples or textual instructions, especially at scale. They also, paradoxically, struggle with basic functionality, such as arithmetic or factual lookup, where much simpler and smaller models excel. In this talk, we show how these limitations can be overcome by letting language models teach themselves to use external tools via simple APIs. We discuss Toolformer, a model trained to independently decide which APIs to call, when to call them, what arguments to pass, and how to best incorporate the results into future token prediction. Through this, it achieves substantially improved zero-shot performance across a variety of downstream tasks without sacrificing its core language modeling abilities.

Boundary current fluctuations for the half space ASEP
2023-04-26 15:30 - 16:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Probability Seminar
Speaker: Jimmy He (MIT)
Title: Boundary current fluctuations for the half space ASEP
Abstract: The half space asymmetric simple exclusion process (ASEP) is an interacting particle system on the half line, with particles allowed to enter/exit at the boundary. I will discuss recent work on understanding fluctuations for the number of particles in the half space ASEP started with no particles, which exhibits the Baik-Rains phase transition between GSE, GOE, and Gaussian fluctuations as the boundary rates vary. As part of the proof, we find new distributional identities relating this system to two other models, the half space Hall-Littlewood process, and the free boundary Schur process, which allows exact formulas to be computed.

The localized seed-to-solution method for the Einstein constraints
2023-04-27 10:30 - 11:30 | Virtual
General Relativity Seminar
Speaker: Philippe G. LeFloch, Sorbonne University and CNRS
Title: The localized seed-to-solution method for the Einstein constraints
Abstract: I will discuss advances on asymptotically Euclidian initial data sets and the variational method introduced by J. Corvino and R. Schoen. This talk is based on joint papers with The-Cang Nguyen (Montpellier) and Bruno Le Floch (Sorbonne Univ. and CNRS). In the vicinity of any given reference data set, we define a “localized seed-to-solution” map, which allows us to parametrize the initial data sets satisfying the Einstein constraints (possibly with matter fields). The parametrization is defined over classes of data sets understood modulo the image of the dual linearized constraints. Our main contribution concerns the sharp behavior of solutions at infinity, which we can arbitrarily localize in asymptotic cones in the sense of A. Carlotto and R. Schoen. Most importantly, as we prove it, the solutions enjoy sharp decay estimates at the harmonic and super-harmonic levels. In the course of this analysis, we discover the notion of ‘asymptotic modulators’, as we call them, or “correctors” to the standard ADM invariants.

Competition at the front of expanding populations
2023-04-27 13:00 - 14:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Active Matter Seminar

Speaker: Mehran Kardar, MIT
Title: Competition at the front of expanding populations
Abstract: When competing species grow into new territory, the population is dominated by descendants of successful ancestors at the expansion front. Successful ancestry depends on the reproductive advantage (fitness), as well as ability and opportunity to colonize new domains. (1) Based on symmetry considerations, we present a model that integrates both elements by coupling the classic description of one-dimensional competition (Fisher equation) to the minimal model of front shape (KPZ equation). Macroscopic manifestations of these equations on growth morphology are explored, providing a framework to study spatial competition, fixation, and differentiation, In particular, we find that ability to expand in space may overcome reproductive advantage in colonizing new territory. (2) Variations of fitness, as well as fixation time upon differentiation, are shown to belong to distinct universality classes depending on limits to gain of fitness.

Fracton Self-Statistics
2023-04-28 10:00 - 11:30 | Virtual
Quantum Matter Seminar
Title: Fracton Self-Statistics
Speaker: Hao Song (ITP-CAS)
Abstract: Fracton order describes novel quantum phases of matter that host quasiparticles with restricted mobility, and thus lies beyond the existing paradigm of topological order. In particular, excitations that cannot move without creating other excitations are called fractons. Here we address a fundamental open question — can the notion of self-exchange statistics be naturally defined for fractons, given their complete immobility as isolated excitations? Surprisingly, we demonstrate how fractons can be exchanged, and show their self-statistics is a key part of the characterization of fracton orders. We derive general constraints satisfied by the fracton self-statistics in a large class of abelian fracton orders. Finally, we show the existence of semionic or fermionic fracton self-statistics in some twisted variants of the checkerboard model and Haah’s code, establishing that these models are in distinct quantum phases as compared to their untwisted cousins.
References: H Song, N Tantivasadakarn, W Shirley, M Hermele, arXiv:2304.00028.

Toroidal Positive Mass Theorem
2023-05-02 12:00 - 13:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Member Seminar
Speaker: Aghil Alaee
Title: Toroidal Positive Mass Theorem
Abstract: In this talk, we review the positive mass conjecture in general relativity and prove a toroidal version of this conjecture in an asymptotically hyperbolic setting.

Generative Adversarial Networks (GANs): An Analytical Perspective
2023-05-03 12:30 - 13:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Speaker: Xin Guo, UC Berkeley
Title: Generative Adversarial Networks (GANs): An Analytical Perspective
Abstract: Generative models have attracted intense interests recently. In this talk, I will discuss one class of generative models, Generative Adversarial Networks (GANs). I will first provide a gentle review of the mathematical framework behind GANs. I will then proceed to discuss a few challenges in GANs training from an analytical perspective. I will finally report some recent progress for GANs training in terms of its stability and convergence analysis.

Random Neural Networks
2023-05-03 15:30 - 16:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Probability Seminar
Speaker: Boris Hanin (Princeton)

Title: Random Neural Networks
Abstract: Fully connected neural networks are described two by structural parameters: a depth L and a width N. In this talk, I will present results and open questions about the asymptotic analysis of such networks with random weights and biases in the regime where N (and potentially L) are large. The first set of results are for deep linear networks, which are simply products of L random matrices of size N x N. I’ll explain how the setting where the ratio L / N is fixed with both N and L large reveals a number of phenomena not present when only one of them is large. I will then state several results about non-linear networks in which this depth-to-width ratio L / N again plays a crucial role and gives an effective notion of depth for a random neural network.

Testing GR with GWs
2023-05-04 09:30 - 10:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
General Relativity Seminar
Speaker: Vitor Cardoso, IST, Lisbon and The Niels Bohr Institute, Copenhagen
Title: Testing GR with GWs
Abstract: One of the most remarkable possibilities of General Relativity concerns gravitational collapse to black holes, leaving behind a geometry with light rings, ergoregions and horizons. These peculiarities are responsible for uniqueness properties and energy extraction mechanisms that turn black holes into ideal laboratories of strong gravity, of particle physics (yes!) and of possible quantum-gravity effects. I will discuss some of the latest progress in tests of General Relativity with black holes.

Detecting central charge in a superconducting quantum processor
2023-05-05 10:00 - 11:30 | Hybrid – G10
Quantum Matter Seminar
Speaker: Sona Najafi (IBM Quantum)
Title: Detecting central charge in a superconducting quantum processor
Abstract: Physical systems at the continuous phase transition point exhibit conformal symmetry rendering local scaling invariance. In two dimensions, the conformal group possesses infinite generators described by Virasoro algebra with an essential parameter known as a central charge. While the central charge manifests itself in a variety of quantities, its detection in experimental setup remains elusive. In this work, we utilize Shannon-Renyi entropy on a local basis of a one-dimensional quantum spin chain at a critical point. We first use a simulated variational quantum eigen solver to prepare the ground state of the critical transfer field Ising model and XXZ model with open and periodic boundary conditions and perform local Pauli X and Z basis measurements. Using error mitigation such as probabilistic error cancellation, we extract an estimation of the local Pauli observables needed to determine the Shannon-Renyi entropy with respect to subsystem size. Finally, we obtain the central charge in the sub-leading term of Shannon-Renyi entropy.

Workshop on Global Categorical Symmetries
2023-05-07 09:00 - 2023-05-12 18:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
The CMSA will be hosting a Workshop on Global Categorical Symmetries from May 7 – 12, 2023
Participation in the workshop is by invitation.
Public Lectures
There will be three lectures on Thursday, May 11, 2023, which are open to the public.
Location: Room G-10, CMSA, 20 Garden Street, Cambridge MA 02138
Note: The public lectures will be held in-person only.
2:00 – 2:50 pm
Speaker: Kantaro Ohmori (U Tokyo )
Title: Fusion Surface Models: 2+1d Lattice Models from Higher Categories
Abstract: Generalized symmetry in general dimensions is expected to be described by higher categories. Conversely, one might expect that, given a higher category with appropriate structures, there exist models that admit the category as its symmetry. In this talk I will explain a construction of such 2+1d lattice models for fusion 2-categories defined by Douglas and Reutter, generalizing the work of Aasen, Fendley and Mong on anyon chains. The construction is by decorating a boundary of a topological Freed-Teleman-Moore sandwich into a non-topological boundary. In particular we can construct a family of candidate lattice systems for chiral topological orders.

3:00 – 3:50 pm
Speaker: David Jordan (Edinburgh)
Title: Langlands duality for 3-manifolds
Abstract: Originating in number theory, and permeating representation theory, algebraic geometry, and quantum field theory, Langlands duality is a pattern of predictions relating pairs of mathematical objects which have no clear a priori mathematical relation. In this talk I’ll explain a new conjectural appearance of Langlands duality in the setting of 3-manifold topology, I’ll give some evidence in the form of special cases, and I’ll survey how the conjecture relates to both the arithmetic and geometric Langlands duality conjectures.
3:50 – 4:30 pm
Tea/Snack Break
4:30 – 5:30 pm
Speaker: Ken Intriligator (UCSD)
Colloquium
Title: QFT Aspects of Symmetry
Abstract: Everything in the Universe, including the photons that we see and the quarks and electrons in our bodies, are actually ripples of quantum fields. Quantum field theory (QFT) is the underlying mathematical framework of Nature, and in the case of electrons and photons it is the most precisely tested theory in science. Strongly coupled aspects, e.g. the confinement of quarks and gluons at long distances, remain challenging. QFT also describes condensed matter systems, connects to string theory and quantum gravity, and describes cosmology. Symmetry has deep and powerful realizations and implications throughout physics, and this is especially so for the study of QFT. Symmetries play a helpful role in characterizing the phases of theories and their behavior under renormalization group flows (zooming out). Quantum field theory has also been an idea generating machine for mathematics, and there has been increasingly fruitful synergy in both directions. We are currently exploring the symmetry-based interconnections between QFT and mathematics in our Simons Collaboration on Global Categorical Symmetry, which is meeting here this week. I will try to provide an accessible, colloquium-level introduction to aspects of symmetries and QFT, both old and new.

Modern Hopfield Networks for Novel Transformer Architectures
2023-05-10 14:00 - 15:00 | Virtual
New Technologies in Mathematics Seminar
Speaker: Dmitry Krotov, IBM Research – Cambridge
Title: Modern Hopfield Networks for Novel Transformer Architectures
Abstract: Modern Hopfield Networks or Dense Associative Memories are recurrent neural networks with fixed point attractor states that are described by an energy function. In contrast to conventional Hopfield Networks, which were popular in the 1980s, their modern versions have a very large memory storage capacity, which makes them appealing tools for many problems in machine learning and cognitive and neurosciences. In this talk, I will introduce an intuition and a mathematical formulation of this class of models and will give examples of problems in AI that can be tackled using these new ideas. Particularly, I will introduce an architecture called Energy Transformer, which replaces the conventional attention mechanism with a recurrent Dense Associative Memory model. I will explain the theoretical principles behind this architectural choice and show promising empirical results on challenging computer vision and graph network tasks.

Insights from single cell lineage trees
2023-05-11 13:00 - 14:00 | MA
Active Matter Seminar

Speaker: Sahand Hormoz, Harvard Medical School, Dana-Farber Cancer Institute

Title: Insights from single cell lineage trees

Abstract: In this talk, I will discuss two recent projects from my lab that involve lineage trees of cells (the branching diagram that represents the ancestry and division history of individual cells). In the first project, we reconstructed the lineage trees of individual cancer cells from the patterns of randomly occurring mutations in these cells. We then inferred the age at which the cancer mutation first occurred and the rate of expansion of the population of cancer cells within each patient. To our surprise, we discovered that the cancer mutation occurs decades before diagnosis. For the second project, we developed microfluidic ‘mother machines’ that allow us to observe mammalian cells dividing across tens of generations. Using our observations, we calculated the correlation between the duration of cell cycle phases in pairs of cells, as a function of their lineage distance. These correlations revealed many surprises that we are trying to understand using hidden Markov models on trees. For both projects, I will discuss the mathematical challenges that we have faced and open problems related to inference from lineage trees.

How do the eigenvalues of a large non-Hermitian random matrix behave?
2023-05-11 13:30 - 14:30 | Harvard Science Center, 1 Oxford Street, Cambridge, MA, 02138
Probability Seminar
Speaker: Giorgio Cipolloni (Princeton)
Title: How do the eigenvalues of a large non-Hermitian random matrix behave?
Abstract: We prove that the fluctuations of the eigenvalues converge to the Gaussian Free Field (GFF) on the unit disk. These fluctuations appear on a non-natural scale, due to strong correlations between the eigenvalues. Then, motivated by the long time behaviour of the ODE dot{u}=Xu, we give a precise estimate on the eigenvalue with the largest real part and on the spectral radius of X.
Location: Science Center Room 232

Positivity of Static quasi-local Mass in general relativity
2023-05-11 13:30 - 14:30 | Virtual
General Relativity Seminar
Speaker: Aghil Alaee, Clark University
Title: Positivity of Static quasi-local Mass in general relativity
Abstract: In this talk, we review results on the PMT of quasi-local masses and prove the positivity of static quasi-local masses with respect to the AdS and AdS Schwarzschild spacetimes.

Anomalies of (1+1)D categorical symmetries
2023-05-12 10:00 - 11:30 | Virtual
Quantum Matter Seminar
Speaker: Carolyn Zhang (U Chicago)
Title: Anomalies of (1+1)D categorical symmetries
Abstract: We present a general approach for detecting when a fusion category symmetry is anomalous, based on the existence of a special kind of Lagrangian algebra of the corresponding Drinfeld center. The Drinfeld center of a fusion category $A$ describes a $(2+1)D$ topological order whose gapped boundaries enumerate all $(1+1)D$ gapped phases with the fusion category symmetry, which may be spontaneously broken. There always exists a gapped boundary, given by the emph{electric} Lagrangian algebra, that describes a phase with $A$ fully spontaneously broken. The symmetry defects of this boundary can be identified with the objects in $A$. We observe that if there exists a different gapped boundary, given by a emph{magnetic} Lagrangian algebra, then there exists a gapped phase where $A$ is not spontaneously broken at all, which means that $A$ is not anomalous. In certain cases, we show that requiring the existence of such a magnetic Lagrangian algebra leads to highly computable obstructions to $A$ being anomaly-free. As an application, we consider the Drinfeld centers of $mathbb{Z}_Ntimesmathbb{Z}_N$ Tambara-Yamagami fusion categories and recover known results from the study of fiber functors.

Quantum information and extended topological quantum field theory
2023-05-15 12:00 - 13:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Member Seminar
Speaker: Gabriel Wong
Title: Quantum information and extended topological quantum field theory
Abstract: Recently, ideas from quantum information theory have played an important role in condensed matter and quantum gravity research. Most of these applications focus on the entanglement structure of quantum states, and the computation of entanglement measures such as entanglement entropy has been an essential part of the story. In this talk, we will address some subtleties that arise when trying to define entanglement entropy in quantum field theory and quantum gravity. In particular, we will explain why extended topological field theory provides a useful framework to define and compute entanglement entropy in a continuous system. Time permitting, we will explain some recent applications of these ideas in low dimensional quantum gravity and to topological string theory.

GRAMSIA: Graphical Models, Statistical Inference, and Algorithms
2023-05-16 09:00 - 2023-05-19 17:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
On May 16 – May 19, 2023 the CMSA hosted a four-day workshop on GRAMSIA: Graphical Models, Statistical Inference, and Algorithms. The workshop was held in room G10 of the CMSA, located at 20 Garden Street, Cambridge, MA. This workshop was organized by David Gamarnik (MIT), Kavita Ramanan (Brown), and Prasad Tetali (Carnegie Mellon).
The purpose of this workshop is to highlight various mathematical questions and issues associated with graphical models and message-passing algorithms, and to bring together a group of researchers for discussion of the latest progress and challenges ahead. In addition to the substantial impact of graphical models on applied areas, they are also connected to various branches of the mathematical sciences. Rather than focusing on the applications, the primary goal is to highlight and deepen these mathematical connections.
Location: Room G10, CMSA, 20 Garden Street, Cambridge MA 02138

Speakers:

Jake Abernethy (Georgia Tech)
Guy Bresler (MIT)
Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
Lester Mackey (Microsoft Research New England)
Theo McKenzie (Harvard)
Andrea Montanari (Stanford)
Elchanan Mossel (MIT)
Yury Polyanskiy (MIT)
Patrick Rebeschini (Oxford)
Subhabrata Sen (Harvard)
Devavrat Shah (MIT)
Pragya Sur (Harvard)
Alex Wein (UC Davis)
Yihong Wu (Yale)
Sarath Yasodharan (Brown)
Horng-Tzer Yau (Harvard)
Christina Lee Yu (Cornell)
Ilias Zadik (MIT)

Schedule:
Tuesday, May 16, 2023

9:00 am
Breakfast

9:15 – 9:30 am
Introductory remarks by organizers

9:30 – 10:20 am
Subhabrata Sen (Harvard)
Title: Mean-field approximations for high-dimensional Bayesian regression
Abstract: Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. The Naive Mean-Field (NMF) approximation is the simplest version of this strategy—this approach approximates the posterior in KL divergence by a product distribution. There has been considerable progress recently in understanding the accuracy of NMF under structural constraints such as sparsity, but not much is known in the absence of such constraints. Moreover, in some high-dimensional settings, the NMF is expected to be grossly inaccurate, and advanced mean-field techniques (e.g. Bethe approximation) are expected to provide accurate approximations. We will present some recent work in understanding this duality in the context of high-dimensional regression. This is based on joint work with Sumit Mukherjee (Columbia) and Jiaze Qiu (Harvard University).

10:30 – 11:00 am
Coffee break

11:00 – 11:50 am
Elchanan Mossel (MIT)
Title: Some modern perspectives on the Kesten-Stigum bound for reconstruction on trees.
Abstract: The Kesten-Stigum bound is a fundamental spectral bound for reconstruction on trees. I will discuss some conjectures and recent progress on understanding when it is tight as well as some conjectures and recent progress on what it signifies even in cases where it is not tight.

12:00 – 2:00 pm
Lunch

2:00 – 2:50 pm
Christina Lee Yu (Cornell)
Title: Exploiting Neighborhood Interference with Low Order Interactions under Unit Randomized Design
Abstract: Network interference, where the outcome of an individual is affected by the treatment assignment of those in their social network, is pervasive in many real-world settings. However, it poses a challenge to estimating causal effects. We consider the task of estimating the total treatment effect (TTE), or the difference between the average outcomes of the population when everyone is treated versus when no one is, under network interference. Under a Bernoulli randomized design, we utilize knowledge of the network structure to provide an unbiased estimator for the TTE when network interference effects are constrained to low order interactions among neighbors of an individual. We make no assumptions on the graph other than bounded degree, allowing for well-connected networks that may not be easily clustered. Central to our contribution is a new framework for balancing between model flexibility and statistical complexity as captured by this low order interactions structure.

3:00 – 3:30 pm
Coffee break

3:30 – 4:20 pm
Theo McKenzie (Harvard)
Title: Spectral statistics for sparse random graphs
Abstract: Understanding the eigenvectors and eigenvalues of the adjacency matrix of random graphs is fundamental to many algorithmic questions; moreover, it is related to longstanding questions in quantum physics. In this talk we focus on random models of sparse graphs, giving some properties that are unique to these sparse graphs, as well as some specific obstacles. Based on this, we show some new results on spectral statistics of sparse random graphs, as well as some conjectures.

4:40 – 6:30 pm
Lightning talk session + welcome reception

Wednesday, May 17, 2023

9:00 am
Breakfast

9:30 – 10:20
Ilias Zadik (MIT)
Title: Revisiting Jerrum’s Metropolis Process for the Planted Clique Problem
Abstract: Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”.
In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992.

10:30 – 11:00
Coffee break

11:00 – 11:50
Florent Krzakala (Ecole Polytechnique Federale de Lausanne)
Title: Are Gaussian data all you need for machine learning theory?
Abstract: Clearly, no! Nevertheless, the Gaussian assumption remains prevalent among theoreticians, particularly in high-dimensional statistics and physics, less so in traditional statistical learning circles. To what extent are Gaussian features merely a convenient choice for certain theoreticians, or genuinely an effective model for learning? In this talk, I will review recent progress on these questions, achieved using rigorous probabilistic approaches in high-dimension and techniques from mathematical statistical physics. I will demonstrate that, despite its apparent limitations, the Gaussian approach is sometimes much closer to reality than one might expect. In particular, I will discuss key findings from a series of recent papers that showcase the Gaussian equivalence of generative models, the universality of Gaussian mixtures, and the conditions under which a single Gaussian can characterize the error in high-dimensional estimation. These results illuminate the strengths and weaknesses of the Gaussian assumption, shedding light on its applicability and limitations in the realm of theoretical statistical learning.

12:00 – 2:00 pm
Lunch

2:00 – 2:50 pm
Andrea Montanari (Stanford)
Title: Dimension free ridge regression
Abstract: Random matrix theory has become a widely useful tool in high-dimensional statistics and theoretical machine learning. However, random matrix theory is largely focused on the proportional asymptotics in which the number of columns grows proportionally to the number of rows of the data matrix. This is not always the most natural setting in statistics where columns correspond to covariates and rows to samples. With the objective to move beyond the proportional asymptotics, we revisit ridge regression. We allow the feature vector to be high-dimensional, or even infinite-dimensional, in which case it belongs to a separable Hilbert space and assume it to satisfy a certain convex concentration property. Within this setting, we establish non-asymptotic bounds that approximate the bias and variance of ridge regression in terms of the bias and variance of an ‘equivalent’ sequence model (a regression model with diagonal design matrix). Previously, such an approximation result was known only in the proportional regime and only up to additive errors: in particular, it did not allow to characterize the behavior of the excess risk when this converges to 0. Our general theory recovers earlier results in the proportional regime (with better error rates). As a new application, we obtain a completely explicit and sharp characterization of ridge regression for Hilbert covariates with regularly varying spectrum. Finally, we analyze the overparametrized near-interpolation setting and obtain sharp ‘benign overfitting’ guarantees.
[Based on joint work with Chen Cheng]

3:00 – 3:50 pm
Yury Polyanskiy (MIT)
Title: Recent results on broadcasting on trees and stochastic block model
Abstract: I will survey recent results and open questions regarding the q-ary stochastic block model and its local version (broadcasting on trees, or BOT). For example, establishing uniqueness of non-trivial solution to distribution recursions (BP fixed point) implies a characterization for the limiting mutual information between the graph and community labels. For q=2 uniqueness holds in all regimes. For q>2 uniqueness is currently only proved above a certain threshold that is asymptotically (for large q) is close to Kesten-Stigum (KS) threshold. At the same time between the BOT reconstruction and KS we show that uniqueness does not hold, at least in the presence of (arbitrary small) vertex-level side information. I will also discuss extension of the robust reconstruction result of Janson-Mossel’2004.
Based on joint works with Qian Yu (Princeton) and Yuzhou Gu (MIT).

4:00 – 4:30 pm
Coffee break

4:30 – 5:20 pm
Alex Wein (UC Davis)
Title: Is Planted Coloring Easier than Planted Clique?
Abstract: The task of finding a planted clique in the random graph G(n,1/2) is perhaps the canonical example of a statistical-computational gap: for some clique sizes, the task is statistically possible but believed to be computationally hard. Really, there are multiple well-studied tasks related to the planted clique model: detection, recovery, and refutation. While these are equally difficult in the case of planted clique, this need not be true in general. In the related planted coloring model, I will discuss the computational complexity of these three tasks and the interplay among them. Our computational hardness results are based on the low-degree polynomial model of computation.By taking the complement of the graph, the planted coloring model is analogous to the planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.

Thursday, May 18, 2023

9:00
Breakfast

9:30 – 10:20
Guy Bresler (MIT)
Title: Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs
Abstract: There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. We develop a new general framework for reasoning about the validity of average-case reductions based on low sensitivity to perturbations. As a concrete instance of our general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). Joint work with Chenghao Guo and Yury Polyanskiy.

10:30 – 11:00
Coffee break

11:00 – 11:50
Sarath Yasodharan (Brown)
Title: A Sanov-type theorem for unimodular marked random graphs and its applications
Abstract: We prove a Sanov-type large deviation principle for the component empirical measures of certain sequences of unimodular random graphs (including Erdos-Renyi and random regular graphs) whose vertices are marked with i.i.d. random variables. Specifically, we show that the rate function can be expressed in a fairly tractable form involving suitable relative entropy functionals. As a corollary, we establish a variational formula for the annealed pressure (or limiting log partition function) for various statistical physics models on sparse random graphs. This is joint work with I-Hsun Chen and Kavita Ramanan.

12:00 – 12:15 pm
12:15 – 2:00 pm
Group Photo
Lunch

2:00 – 2:50 pm
Patrick Rebeschini (Oxford)
Title: Implicit regularization via uniform convergence
Abstract: Uniform convergence is one of the main tools to analyze the complexity of learning algorithms based on explicit regularization, but it has shown limited applicability in the context of implicit regularization. In this talk, we investigate the statistical guarantees on the excess risk achieved by early-stopped mirror descent run on the unregularized empirical risk with the squared loss for linear models and kernel methods. We establish a direct link between the potential-based analysis of mirror descent from optimization theory and uniform learning. This link allows characterizing the statistical performance of the path traced by mirror descent directly in terms of localized Rademacher complexities of function classes depending on the choice of the mirror map, initialization point, step size, and the number of iterations. We will discuss other results along the way.

3:00 – 3:50 pm
Pragya Sur (Harvard)
Title: A New Central Limit Theorem for the Augmented IPW estimator in high dimensions
Abstract: Estimating the average treatment effect (ATE) is a central problem in causal inference. Modern advances in the field studied estimation and inference for the ATE in high dimensions through a variety of approaches. Doubly robust estimators such as the augmented inverse probability weighting (AIPW) form a popular approach in this context. However, the high-dimensional literature surrounding these estimators relies on sparsity conditions, either on the outcome regression (OR) or the propensity score (PS) model. This talk will introduce a new central limit theorem for the classical AIPW estimator, that applies agnostic to such sparsity-type assumptions. Specifically, we will study properties of the cross-fit version of the estimator under well-specified OR and PS models, and the proportional asymptotics regime where the number of confounders and sample size diverge proportional to each other. Under assumptions on the covariate distribution, our CLT will uncover two crucial phenomena among others: (i) the cross-fit AIPW exhibits a substantial variance inflation that can be quantified in terms of the signal-to-noise ratio and other problem parameters, (ii) the asymptotic covariance between the estimators used while cross-fitting is non-negligible even on the root-n scale. These findings are strikingly different from their classical counterparts, and open a vista of possibilities for studying similar other high-dimensional effects. On the technical front, our work utilizes a novel interplay between three distinct tools—approximate message passing theory, the theory of deterministic equivalents, and the leave-one-out approach.

4:00 – 4:30 pm
Coffee break

4:30 – 5:20 pm
Yihong Wu (Yale)
Title: Random graph matching at Otter’s threshold via counting chandeliers

Abstract: We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nqtoinfty and the edge correlation coefficient ρ satisfies ρ^2>α≈0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. This is joint work with Cheng Mao, Jiaming Xu, and Sophie Yu, available at https://arxiv.org/abs/2209.12313

Friday, May 19, 2023

9:00
Breakfast

9:30 – 10:20
Jake Abernethy (Georgia Tech)
Title: Optimization, Learning, and Margin-maximization via Playing Games
Abstract: A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, including optimization, learning, and margin-maximiation problems. Along the way we will encounter a number of novel tools and rediscover some classical ones as well.

10:30 – 11:00
Coffee break

11:00 – 11:50
Devavrat Shah (MIT)
Title: On counterfactual inference with unobserved confounding via exponential family
Abstract: We are interested in the problem of unit-level counterfactual inference with unobserved confounders owing to the increasing importance of personalized decision-making in many domains: consider a recommender system interacting with a user over time where each user is provided recommendations based on observed demographics, prior engagement levels as well as certain unobserved factors. The system adapts its recommendations sequentially and differently for each user. Ideally, at each point in time, the system wants to infer each user’s unknown engagement if it were exposed to a different sequence of recommendations while everything else remained unchanged. This task is challenging since: (a) the unobserved factors could give rise to spurious associations, (b) the users could be heterogeneous, and (c) only a single trajectory per user is available.
We model the underlying joint distribution through an exponential family. This reduces the task of unit-level counterfactual inference to simultaneously learning a collection of distributions of a given exponential family with different unknown parameters with single observation per distribution. We discuss a computationally efficient method for learning all of these parameters with estimation error scaling linearly with the metric entropy of the space of unknown parameters – if the parameters are an s-sparse linear combination of k known vectors in p dimension, the error scales as O(s log k/p). En route, we derive sufficient conditions for compactly supported distributions to satisfy the logarithmic Sobolev inequality.
Based on a joint work with Raaz Dwivedi, Abhin Shah and Greg Wornell (all at MIT) with manuscript available here: https://arxiv.org/abs/2211.08209

12:00 – 2:00 pm
Lunch

2:00 – 2:50 pm
Lester Mackey (Microsoft Research New England)
Title: Advances in Distribution Compression
Abstract: This talk will introduce two new tools for summarizing a probability distribution more effectively than independent sampling or standard Markov chain Monte Carlo thinning:
1. Given an initial n-point summary (for example, from independent sampling or a Markov chain), kernel thinning finds a subset of only square-root n-points with comparable worst-case integration error across a reproducing kernel Hilbert space.
2. If the initial summary suffers from biases due to off-target sampling, tempering, or burn-in, Stein thinning simultaneously compresses the summary and improves the accuracy by correcting for these biases.
These tools are especially well-suited for tasks that incur substantial downstream computation costs per summary point like organ and tissue modeling in which each simulation consumes 1000s of CPU hours.
Based on joint work with Raaz Dwivedi, Marina Riabiz, Wilson Ye Chen, Jon Cockayne, Pawel Swietach, Steven A. Niederer, Chris. J. Oates, Abhishek Shetty, and Carles Domingo-Enrich.

3:00 – 3:30 pm
Coffee break

3:30 – 4:20 pm
Horng-Tzer Yau (Harvard)
Title: On the spectral gap of mean-field spin glass models.
Abstract: We will discuss recent progress regarding spectral gaps for the Glauber dynamics of spin glasses at high temperature. In addition, we will also report on estimating the operator norm of the covariance matrix for the SK model.

Moderators: Benjamin McKenna, Harvard CMSA & Changji Xu, Harvard CMSA

CMSA COVID-19 Policies

Classification of Self-Dual Vertex Operator Superalgebras of Central Charge at Most 24
2023-06-09 10:00 - 11:30 | Virtual
Quantum Matter Seminar
Speakers: Gerald Höhn (Kansas State University) & Sven Möller (University of Hamburg)
Title: Classification of Self-Dual Vertex Operator Superalgebras of Central Charge at Most 24
Abstract: We discuss the classfication of self-dual vertex operator superalgebras (SVOAs) of central charge 24, or in physics parlance the purely chiral 2-dimensional fermionic conformal field theories with just one primary field.
There are exactly 969 such SVOAs under suitable regularity assumptions and the assumption that the shorter moonshine module VB^# is the unique self-dual SVOA of central charge 23.5 whose weight-1/2 and weight-1 spaces vanish.
We construct and classify the self-dual SVOAs by determining the 2-neighbourhood graph of the self-dual (purely bosonic) VOAs of central charge 24 and also by realising them as simple-current extensions of a dual pair containing a certain maximal lattice VOA. We show that all SVOAs besides VB^# x F and potential fake copies thereof stem from elements of the Conway group Co_0, the automorphism group of the Leech lattice.
By splitting off free fermions F, if possible, we obtain the classification for all central charges less than or equal to 24.
Reference: G. Höhn, S. Möller, arXiv:2303.17190.

Small Bosonic CFTs, Chiral Fermionization, and Symmetry/Subalgebra Duality
2023-06-13 10:00 - 12:00 | Virtual
Quantum Matter Seminar
Speaker: Brandon C. Rayhaun (C. N. Yang ITP, Stony Brook University)
Title: Small Bosonic CFTs, Chiral Fermionization, and Symmetry/Subalgebra Duality
Abstract: Conformal field theories in (1+1)D are key actors in many dramas of physics and mathematics. Their classification has therefore been an important and long-standing problem. In this talk, I will explain the main ideas behind the classification of (most) “small” bosonic CFTs. Here, I use the adjective “small” informally to refer to theories with low central charge (less than 24) and few primary operators (less than 5). Time and attention permitting, I will highlight two applications of this result. First, I will describe how it can be used in tandem with bosonization and fermionization techniques to establish the classification of chiral fermionic CFTs with central charge less than 23. Second, I will showcase how it can be used to bootstrap generalized global symmetries using the concept of “symmetry/subalgebra duality.”
Talk based on arXiv:2208.05486 [hep-th] (joint work with Sunil Mukhi) and arXiv:2303.16921 [hep-th].

Chiral fermionic CFTs of central charge ≤ 16
2023-06-26 10:00 - 11:30 | Virtual
Quantum Matter Seminar
Title: Chiral fermionic CFTs of central charge ≤ 16
Abstract: We classified all chiral fermionic CFTs of central charge ≤ 16 using Kac’s theorem and bosonization/fermionization. This talk will discuss the derivation of this result, its application to the classification of non-supersymmetric heterotic string theories, and along the way we’ll address some oft-overlooked subtleties of bosonization from the point of view of anomalies and topological phases.
