Date  Speaker  Title/Abstract 
9/28/2018
*Friday, 10:00am* 
Yash Deshpande (MIT)  Title: Estimating lowrank matrices in noise: phase transitions from spin glass theory
Abstract: Estimating lowrank matrices from noisy observations is a common task in statistical and engineering applications. Following the seminal work of Johnstone, Baik, BenArous and Peche, versions of this problem have been extensively studied using random matrix theory. In this talk, we will consider an alternative viewpoint based on tools from mean field spin glasses. We will present two examples that illustrate how these tools yield information beyond those from classical random matrix theory. The first example is the twogroups stochastic block model (SBM), where we will obtain a full informationtheoretic understanding of the estimation phase transition. In the second example, we will augment the SBM with covariate information at nodes, and obtain results on the altered phase transition. This is based on joint works with Emmanuel Abbe, Andrea Montanari, Elchanan Mossel and Subhabrata Sen. 
10/3/2018  Ian Jauslin (IAS)  Title: Liquid Crystals and the HeilmannLieb model
Abstract: In 1979, O.Heilmann and E.H. Lieb introduced an interacting dimer model with the goal of proving the emergence of a nematic liquid crystal phase in it. In such a phase, dimers spontaneously align, but there is no long range translational order. Heilmann and Lieb proved that dimers do, indeed, align, and conjectured that there is no translational order. I will discuss a recent proof of this conjecture. This is joint work with Elliott H. Lieb. 
10/10/2018  Afonso Bandeira (NYU  Title: Statistical estimation under group actions: The Sample Complexity of MultiReference Alignment
Abstract: Many problems in signal/image processing, and computer vision amount to estimating a signal, image, or tridimensional structure/scene from corrupted measurements. A particularly challenging form of measurement corruption are latent transformations of the underlying signal to be recovered. Many such transformations can be described as a group acting on the object to be recovered. Examples include the Simulatenous Localization and Mapping (SLaM) problem in Robotics and Computer Vision, where pictures of a scene are obtained from different positions and orientations; CryoElectron Microscopy (CryoEM) imaging where projections of a molecule density are taken from unknown rotations, and several others. One fundamental example of this type of problems is MultiReference Alignment: Given a group acting in a space, the goal is to estimate an orbit of the group action from noisy samples. For example, in one of its simplest forms, one is tasked with estimating a signal from noisy cyclically shifted copies. We will show that the number of observations needed by any method has a surprising dependency on the signaltonoise ratio (SNR), and algebraic properties of the underlying group action. Remarkably, in some important cases, this sample complexity is achieved with computationally efficient methods based on computing invariants under the group of transformations. 
10/17/2018
3:30pm 
Thomas Chen (UT Austin)  Title: Dynamics of a heavy quantum tracer particle in a Bose gas
Abstract: We consider the dynamics of a heavy quantum tracer particle coupled to a nonrelativistic boson field in R^3. The pair interactions of the bosons are of meanfield type, with coupling strength proportional to 1/N where N is the expected particle number. Assuming that the mass of the tracer particle is proportional to N, we derive generalized Hartree equations in the limit where N tends to infinity. Moreover, we prove the global wellposedness of the associated Cauchy problem for sufficiently weak interaction potentials. This is joint work with Avy Soffer (Rutgers University). 
10/24/2018
*Room G02* 
Tselil Schramm (Harvard/MIT)  Title: (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs
Abstract: The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two notnecessarilyisomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular averagecase variant; we deviate from the common heuristic strategy and give the first quasipolynomial time algorithm, where previously only subexponential time algorithms were known. Based on joint work with Boaz Barak, ChiNing Chou, Zhixian Lei, and Yueqi Sheng. 
10/30/2018
*Tuesday 10:30am SC 507* 
Lauren Williams (Harvard)  Title: Introduction to the asymmetric simple exclusion process (from a combinatorialist’s point of view)
Abstract: The asymmetric simple exclusion process (ASEP) is a model of particles hopping on a onedimensional lattice, subject to the condition that there is at most one particle per site. This model was introduced in 1970 by biologists (as a model for translation in protein synthesis) but has since been shown to display a rich mathematical structure. There are many variants of the model — e.g. the lattice could be a ring, or a line with open boundaries. One can also allow multiple species of particles with different “weights.” I will explain how one can give combinatorial formulas for the stationary distribution using various kinds of tableaux. I will also explain how the ASEP is related to interesting families of orthogonal polynomials, including AskeyWilson polynomials, Koornwinder polynomials, and Macdonald polynomials. 
11/7/2018  Willhelm Schlag (Yale)  Title: on the BourgainDyatlov fractal uncertainty principle
Abstract: We will present the BourgainDyatlov theorem on the line, it’s connection with other uncertainty principles in harmonic analysis, and my recent partial progress with Rui Han on the problem of higher dimensions. 
11/14/2018  David Gamarnik (MIT)  Title: Two Algorithmic Hardness Results in Spin Glasses and Compressive Sensing.
Abstract: I will discuss two computational problems in the area of random combinatorial structures. The first one is the problem of computing the partition function of a SherringtonKirkpatrick spin glass model. While the the problem of computing the partition functions associated with arbitrary instances is known to belong to the #P complexity class, the complexity of the problem for random instances is open. We show that the problem of computing the partition function exactly (in an appropriate sense) for the case of instances involving Gaussian couplings is #Phard on average. The proof uses Lipton’s trick of computation modulo large prime number, reduction of the average case to the worst case instances, and the near uniformity of the ”stretched” lognormal distribution. In the second part we will discuss the problem of explicit construction of matrices satisfying the Restricted Isometry Property (RIP). This challenge arises in the field of compressive sensing. While random matrices are known to satisfy the RIP with high probability, the problem of explicit (deterministic) construction of RIP matrices eluded efforts and hits the socalled ”square root” barrier which I will discuss in the talk. Overcoming this barrier is an open problem explored widely in the literature. We essentially resolve this problem by showing that an explicit construction of RIP matrices implies an explicit construction of graphs satisfying a very strong form of Ramsey property, which has been open since the seminal work of Erdos in 1947. 
11/28/2018  Sean O’ Rourke (UC Boulder)  Title: Universality and least singular values of random matrix products
Abstract: We consider the product of m independent iid random matrices as m is fixed and the sizes of the matrices tend to infinity. In the case when the factor matrices are drawn from the complex Ginibre ensemble, Akemann and Burda computed the limiting microscopic correlation functions. In particular, away from the origin, they showed that the limiting correlation functions do not depend on m, the number of factor matrices. We show that this behavior is universal for products of iid random matrices under a moment matching hypothesis. In addition, we establish universality results for the linear statistics for these product models, which show that the limiting variance does not depend on the number of factor matrices either. The proofs of these universality results require a nearoptimal lower bound on the least singular value for these product ensembles. 
12/5/2018
*Room G02* 
Omer Angel (UBC)  Title: balanced excited random walks
Abstract: I will present results on the scaling limit and asymptotics of the balanced excited random walk and related processes. This is a walk the that moves vertically on the first visit to a vertex, and horizontally on every subsequent visit. We also analyze certain versions of “clairvoyant scheduling” of random walks. Joint work with Mark Holmes and Alejandro Ramirez. 
2/7/2019
Science Center 530 
Ramis Movassagh (IMB Research)  Title: Generic Gaplessness, and Hamiltonian density of states from free probability theory
Abstract: Quantum manybody systems usually reside in their lowest energy states. This among other things, motives understanding the gap, which is generally an undecidable problem. Nevertheless, we prove that generically local quantum Hamiltonians are gapless in any dimension and on any graph with bounded maximum degree. We then provide an applied and approximate answer to an old problem in pure mathematics. Suppose the eigenvalue distributions of two matrices M_1 and M_2 are known. What is the eigenvalue distribution of the sum M_1+M_2? This problem has a rich pure mathematics history dating back to H. Weyl (1912) with many applications in various fields. Free probability theory (FPT) answers this question under certain conditions. We will describe FPT and show examples of its powers for approximating physical quantities such as the density of states of the Anderson model, quantum spin chains, and gapped vs. gapless phases of some Floquet systems. These physical quantities are often hard to compute exactly (provably NPhard). Nevertheless, using FPT and other ideas from random matrix theory excellent approximations can be obtained. Besides the applications presented, we believe the techniques will find new applications in fresh new contexts. 
2/14/2019  Nike Sun (MIT)  Title: Capacity lower bound for the Ising perceptron
Abstract: The perceptron is a toy model of a simple neural network that stores a collection of given patterns. Its analysis reduces to a simple problem in highdimensional geometry, namely, understanding the intersection of the cube (or sphere) with a collection of random halfspaces. Despite the simplicity of this model, its highdimensional asymptotics are not well understood. I will describe what is known and present recent results. 
2/21/2019  Michael Loss (Georgia Tech)  Title: Some results for functionals of AharonovBohm type
Abstract: In this talk I present some variational problems of AharonovBohm type, i.e., they include a magnetic flux that is entirely concentrated at a point. This is maybe the simplest example of a variational problems for systems, the wave function being necessarily complex. The functional is rotationally invariant and the issue to be discussed is whether the optimizer have this symmetry or whether it is broken. 
3/6/2019
4:15pm Science Center 411 
Ilya Kachkovskiy (Michigan State University)  Title: Localization and delocalization for interacting 1D quasiperiodic particles.
Abstract: We consider a system of two interacting onedimensional quasiperiodic particles as an operator on $\ell^2(\mathbb Z^2)$. The fact that particle frequencies are identical, implies a new effect compared to generic 2D potentials: the presence of large coupling localization depends on symmetries of the singleparticle potential. If the potential has no cosinetype symmetries, then we are able to show large coupling localization at all energies, even if the interaction is not small (with some assumptions on its complexity). If symmetries are present, we can show localization away from finitely many energies, thus removing a fraction of spectrum from consideration. We also demonstrate that, in the symmetric case, delocalization can indeed happen if the interaction is strong, at the energies away from the bulk spectrum. The result is based on joint works with Jean Bourgain and Svetlana Jitomirskaya. 
3/14/2019
5:45pm Science Center 232 
Anna Vershynina (University of Houston)  Title: How fast can entanglement be generated in quantum systems?
Abstract: We investigate the maximal rate at which entanglement can be generated in bipartite quantum systems. The goal is to upper bound this rate. All previous results in closed systems considered entanglement entropy as a measure of entanglement. I will present recent results, where entanglement measure can be chosen from a large class of measures. The result is derived from a general bound on the tracenorm of a commutator, and can, for example, be applied to bound the entanglement rate for Renyi and Tsallis entanglement entropies. 
3/28/2019
Room G02 
Xuwen Chen (University of Rochester)  Title: The Derivation of the Energycritical NLS from Quantum Manybody Dynamics
Abstract: We derive the 3D energycritical quintic NLS from quantum manybody dynamics with 3body interaction in the T^3 (periodic) setting. Due to the known complexity of the energy critical setting, previous progress was limited in comparison to the 2body interaction case yielding energy subcritical cubic NLS. We develop methods to prove the convergence of the BBGKY hierarchy to the infinite GrossPitaevskii (GP) hierarchy, and separately, the uniqueness of large GP solutions. Since the trace estimate used in the previous proofs of convergence is the false sharp trace estimate in our setting, we instead introduce a new frequency interaction analysis and apply the finite dimensional quantum de Finetti theorem. For the large solution uniqueness argument, we discover the new HUFL (hierarchical uniform frequency localization) property for the GP hierarchy and use it to prove a new type of uniqueness theorem. 
4/4/2019  Paul Bourgade (NYU)  Title: Logcorrelations and branching structures in analytic number theory
Abstract: Fyodorov, Hiary and Keating have predicted the size of local maxima of Lfunction along the critical axis, based on analogous random matrix statistics. I will explain this prediction in the context of the logcorrelated universality class and branching structures. In particular I will explain why the Riemann zeta function exhibits logcorrelations, and outline the proof for the leading order of the maximum in the Fyodorov, Hiary and Keating prediction. Joint work with Arguin, Belius, Radziwill and Soundararajan. 
4/9/2019
Tuesday 12:00pm Room G02 
Giulio Biroli (ENS Paris)  Title: Large deviations for the largest eigenvalues and eigenvectors of spiked random matrices
Abstract: I consider matrices formed by a random $N\times N$ matrix drawn from the Gaussian Orthogonal Ensemble (or Gaussian Unitary Ensemble) plus a rankone perturbation of strength $\theta$, and focus on the largest eigenvalue, $x$, and the component, $u$, of the corresponding eigenvector in the direction associated to the rankone perturbation. I will show how to obtain the large deviation principle governing the atypical joint fluctuations of $x$ and $u$. Interestingly, for $\theta>1$, in large deviations characterized by a small value of $u$, i.e. $u<11/\theta$, the secondlargest eigenvalue pops out from the Wigner semicircle and the associated eigenvector orients in the direction corresponding to the rankone perturbation. These results can be generalized to the Wishart Ensemble, and extended to the first $n$ eigenvalues and the associated eigenvectors. Finally, I will discuss motivations and applications of these results to the study of the geometric properties of random highdimensional functions—a topic that is currently attracting a lot of attention in physics and computer science. 
4/11/2019  Rui Han (Georgia Tech)  Title: Spectral gaps in graphene structures
Abstract: We present a full analysis of the spectrum of graphene in magnetic fields with constant flux through every hexagonal comb. In particular, we provide a rigorous foundation for selfsimilarity by showing that for irrational flux, the spectrum of graphene is a zero measure Cantor set. We also show that for vanishing flux, the spectral bands have nontrivial overlap, which proves the discrete BetheSommerfeld conjecture for the graphene structure. This is based on joint works with S. Becker, J. Fillman and S. Jitomirskaya. 
4/25/2019  Benjamin Fehrman (Oxford)  Title: Pathwise wellposedness of nonlinear diffusion equations with nonlinear, conservative noise
Abstract: We present a pathwise wellposedness theory for stochastic porous media and fast diffusion equations driven by nonlinear, conservative noise. Such equations arise in the theory of mean field games, approximate the DeanKawasaki equation in fluctuating fluid dynamics, describe the fluctuating hydrodynamics of the zero range process, and model the evolution of a thin film in the regime of negligible surface tension. Motivated by the theory of stochastic viscosity solutions, we pass to the equation’s kinetic formulation, where the noise enters linearly and can be inverted using the theory of rough paths. The talk is based on joint work with Benjamin Gess. 
4/30/2019  TBA  TBA 
5/2/2019  Jian Ding (UPenn)  TBA 
Date…………  Name…………….  Title/Abstract 
21620183:30pm
G02 
Reza Gheissari (NYU)  Dynamics of Critical 2D Potts ModelsAbstract: The Potts model is a generalization of the Ising model to $q\geq 3$ states with inverse temperature $\beta$. The Gibbs measure on $\mathbb Z^2$ has a sharp transition between a disordered regime when $\beta<\beta_c(q)$ and an ordered regime when $\beta>\beta_c(q)$. At $\beta=\beta_c(q)$, when $q\leq 4$, the phase transition is continuous while when $q>4$, the phase transition is discontinuous and the disordered and ordered phases coexist.
We will discuss recent progress, joint with E. Lubetzky, in analyzing the time to equilibrium (mixing time) of natural Markov chains (e.g., heat bath/Metropolis) for the 2D Potts model, where the mixing time on an $n \times n$ torus should transition from $O(\log n)$ at high temperatures to $\exp(c_\beta n)$ at low temperatures, via a critical slowdown at $\beta_c(q)$ that is polynomial in $n$ when $q \leq 4$ and exponential in $n$ when $q>4$. 
22320183:30pm
G02 
Mustazee Rahman (MIT)  On shocks in the TASEPAbstract: The TASEP particle system runs into traffic jams when the particle density to the left is smaller than the density to the right. Macroscopically, the particle density solves Burgers’ equation and traffic jams correspond to its shocks. I will describe work with Jeremy Quastel on a specialization of the TASEP shock whereby we identify the microscopic fluctuations around the shock by using exact formulas for the correlation functions of TASEP and its KPZ scaling limit. The resulting laws are related to universal laws of random matrix theory.
For the curious, here is a video of the shock forming in Burgers’ equation: https://www.youtube.com/watch?v=kU91ciSkmwY 
42020182:003:00pm  Carlo Lucibello(Microsoft Research NE)  The Random Perceptron Problem: thresholds, phase transitions, and geometryAbstract: The perceptron is the simplest feedforward neural network model, the building block of the deep architectures used in modern machine learning practice. In this talk, I will review some old and new results, mostly focusing on the case of binary weights and random examples. Despite its simplicity, this model provides an extremely rich phenomenology: as the number of examples per synapses is increased, the system undergoes different phase transitions, which can be directly linked to solvers’ performances and to information theoretic bounds. A geometrical analysis of the solution space shows how two different types of solutions, akin to wide and sharp minima, have different generalization capabilities when presented with new examples. Solutions in dense clusters generalize remarkably better, partially closing the gap with Bayesian optimal estimators. Most of the results I will present were first obtained using non rigorous techniques from spin glass theory and many of them haven’t been rigorously established yet, although some big steps forward have been taken in recent years. 
42020183:004:00pm  Yash Despande(MIT)  Phase transitions in estimating lowrank matricesAbstract: Lowrank perturbations of Wigner matrices have been extensively studied in random matrix theory; much information about the corresponding spectral phase transition can be gleaned using these tools. In this talk, I will consider an alternative viewpoint based on tools from spin glass theory, and two examples that illustrate how these they yield information beyond traditional spectral tools. The first example is the stochastic block model,where we obtain a full informationtheoretic picture of estimation. The second example demonstrates how side information alters the spectral threshold. It involves a new phase transition that interpolates between the Wigner and Wishart ensembles. 
Date  Name  Title/Abstract 
92717  Herbert Spohn, Technische Universität München  Hydrodynamics of integrable classical and quantum systems
Abstract: In the cold atoms community there is great interest in developing Eulertype hydrodynamics for onedimensional integrable quantum systems, in particular with application to domain wall initial states. I provide some mathematical physics background and also compare with integrable classical systems. 
102317
*12:001:00pm, Science Center 232* 
Madhu Sudan, Harvard SEAS  General Strong Polarization
A recent discovery (circa 2008) in information theory called Polar Coding has led to a remarkable construction of errorcorrecting codes and decoding algorithms, resolving one of the fundamental algorithmic challenges in the field. The underlying phenomenon studies the “polarization” of a “bounded” martingale. A bounded martingale, X_0,…,X_t,… is one where X_t in [0,1]. This martingale is said to polarize if Pr[lim_{t\to infty} X_t \in {0,1}] = 1. The questions of interest to the results in coding are the rate of convergence and proximity: Specifically, given epsilon and tau > 0 what is the smallest t after which it is the case that Pr[X_t in (tau,1tau)] < epsilon? For the main theorem, it was crucial that t <= min{O(log(1/epsilon)), o(log(1/tau))}. We say that a martingale polarizes strongly if it satisfies this requirement. We give a simple local criterion on the evolution of the martingale that suffices for strong polarization. A consequence to coding theory is that a broad class of constructions of polar codes can be used to resolve the aforementioned algorithmic challenge. In this talk I will introduce the concepts of polarization and strong polarization. Depending on the audience interest I can explain why this concept is useful to construct codes and decoding algorithms, or explain the local criteria that help establish strong polarization (and the proof of why it does so). Based on joint work with Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, and Atri Rudra. 
102517
*2:004:00pm* 
Subhabrata Sen (Microsoft and MIT)
Noga Alon,(Tel Aviv University) 
Subhabrata Sen, “Partitioning sparse random graphs: connections with meanfield spin glasses”
Abstract: The study of graphpartition problems such as Maxcut, maxbisection and minbisection have a long and rich history in combinatorics and theoretical computer science. A recent line of work studies these problems on sparse random graphs, via a connection with mean field spin glasses. In this talk, we will look at this general direction, and derive sharp comparison inequalities between cutsizes on sparse Erd\ ̋{o}sR\'{e}nyi and random regular graphs. Based on joint work with Aukosh Jagannath. Noga Alon, “Random Cayley Graphs” Abstract: The study of random Cayley graphs of finite groups is related to the investigation of Expanders and to problems in Combinatorial Number Theory and in Information Theory. I will discuss this topic, describing the motivation and focusing on the question of estimating the chromatic number of a random Cayley graph of a given group with a prescribed number of generators. Several intriguing questions that remain open will be mentioned as well. 
11117
*2:004:00pm* 
Kay Kirkpatrick (Illinois)
and WeiMing Wang (CNRS) 
Kay Kirkpatrick, Quantum groups, Free ArakiWoods Factors, and a Calculus for Moments
Abstract: We will discuss a central limit theorem for quantum groups: that the joint distributions with respect to the Haar state of the generators of free orthogonal quantum groups converge to free families of generalized circular elements in the large (quantum) dimension limit. We also discuss a connection to free ArakiWoods factors, and cases where we have surprisingly good rates of convergence. This is joint work with Michael Brannan. Time permitting, we’ll mention another quantum central limit theorem for BoseEinstein condensation and work in progress. WeiMin Wang, Quasiperiodic solutions to nonlinear PDE’s Abstract: We present a new approach to the existence of time quasiperiodic solutions to nonlinear PDE’s. It is based on the method of Anderson localization, harmonic analysis and algebraic analysis. This can be viewed as an infinite dimensional analogue of a Lagrangian approach to KAM theory, as suggested by J. Moser. 
11817  Elchanan Mossel  Optimal Gaussian Partitions.
Abstract: How should we partition the Gaussian space into k parts in a way that minimizes Gaussian surface area, maximize correlation or simulate a specific distribution. The problem of Gaussian partitions was studied since the 70s first as a generalization of the isoperimetric problem in the context of the heat equation. It found a renewed interest in context of the double bubble theorem proven in geometric measure theory and due to connection to problems in theoretical computer science and social choice theory. I will survey the little we know about this problem and the major open problems in the area. 
111017
*12pm SC 232* 
Zhe Wang (NYU)  A Driven Tagged Particle in Onedimensional Simple Exclusion Process
Abstract: We study the longtime behavior of a driven tagged particle in a onedimensional nonnearest neighbor simple exclusion process. We will discuss two scenarios when the tagged particle has a speed. Particularly, for the ASEP, the tagged particle can have a positive speed even when it has a drift with negative mean; for the SSEP with removals, we can compute the speed explicitly. We will characterize some nontrivial invariant measures of the environment process by using coupling arguments and color schemes. 
111517
*4:005:00pm* *G02* 
Daniel Sussman (BU)  Multiple Network Inference: From Joint Embeddings to Graph Matching
Abstract: Statistical theory, computational methods, and empirical evidence abound for the study of individual networks. However, extending these ideas to the multiplenetwork framework remains a relatively underexplored area. Individuals today interact with each other through numerous modalities including online social networks, telecommunications, facetoface interactions, financial transactions, and the sharing and distribution of goods and services. Individually these networks may hide important activities that are only revealed when the networks are studied jointly. In this talk, we’ll explore statistical and computational methods to study multiple networks, including a tool to borrow strength across networks via joint embeddings and a tool to confront the challenges of entity resolution across networks via graph matching. 
112017
*Monday 12:001:00pm* 
Yue M. Lu
(Harvard) 
Asymptotic Methods for HighDimensional Inference: Precise Analysis, Fundamental Limits, and Optimal Designs
Abstract: Extracting meaningful information from the large datasets being compiled by our society presents challenges and opportunities to signal and information processing research. On the one hand, many classical methods, and the assumptions they are based on, are simply not designed to handle the explosive growth of the dimensionality of the modern datasets. On the other hand, the increasing dimensionality offers many benefits: in particular, the very highdimensional settings allow one to apply powerful asymptotic methods from probability theory and statistical physics to obtain precise characterizations that would otherwise be too complicated in moderate dimensions. I will mention recent work on exploiting such blessings of dimensionality via sharp asymptotic methods. In particular, I will show (1) the exact characterization of a widelyused spectral method for nonconvex signal recoveries; (2) the fundamental limits of solving the phase retrieval problem via linear programming; and (3) how to use scaling and meanfield limits to analyze nonconvex optimization algorithms for highdimensional inference and learning. In these problems, asymptotic methods not only clarify some of the fascinating phenomena that emerge with highdimensional data, they also lead to optimal designs that significantly outperform commonly used heuristic choices.

112917  David Gamarink (MIT)  (Arguably) Hard on Average Constraint Satisfaction Problems
Abstract: Many combinatorial optimization problems defined on random instances such as random graphs, exhibit an apparent gap between the optimal value, which can be estimated by nonconstructive means, and the best values achievable by fast (polynomial time) algorithms. Through a combined effort of mathematicians, computer scientists and statistical physicists, it became apparent that a potential and in some cases a provable obstruction for designing algorithms bridging this gap is an intricate geometry of nearly optimal solutions, in particular the presence of chaos and a certain Overlap Gap Property (OGP), which we will introduce in this talk. We will demonstrate how for many such problems, the onset of the OGP phase transition indeed nearly coincides with algorithmically hard regimes. Our examples will include the problem of finding a largest independent set of a graph, finding a largest cut in a random hypergrah, random NAEKSAT problem, the problem of finding a largest submatrix of a random matrix, and a highdimensional sparse linear regression problem in statistics. Joint work with WeiKuo Chen, Quan Li, Dmitry Panchenko, Mustazee Rahman, Madhu Sudan and Ilias Zadik. 
12617
*2:004:00pm* 
Philippe Rigollet (MIT)
23 pm & Ankur Moitra (MIT) 34 pm 
Philippe Rigollet (MIT), Exact Recovery in the Ising Block Model
Abstract: Over the past fifteen years, the problem of learning Ising models from independent samples has been of significant interest in the statistics, machine learning, and statistical physics communities. Much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models, primarily in the case where the interaction graph is sparse. In parallel, stochastic blockmodels have played a more and more preponderant role in community detection and clustering as an average case model for the minimum bisection model. In this talk, we introduce a new model, called Ising blockmodel for the community structure in an Ising model. It imposes a block structure on the interactions of a dense Ising model and can be viewed as a structured perturbation of the celebrated CurieWeiss model. We show that interesting phase transitions arise in this model and leverage this probabilistic analysis to develop an algorithm based on semidefinite programming that recovers exactly the community structure when the sample size is large enough. We also prove that exact recovery of the block structure is actually impossible with fewer samples. This is joint work with Quentin Berthet (University of Cambridge) and Piyush Srivastava (Tata Institute). Ankur Moitra (MIT), A New Approach to Approximate Counting and Sampling Abstract: Over the past sixty years, many remarkable connections have been made between statistical physics, probability, analysis and theoretical computer science through the study of approximate counting. While tight phase transitions are known for many problems with pairwise constraints, much less is known about problems with higherorder constraints. 
121417  TBD  