Previous Random Matrix & Probability Theory Seminars

 

Date………… Name……………. Title/Abstract
2-16-20183: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$.

2-23-20183: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

4-20-20182:00-3: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.
4-20-20183:00-4:00pm Yash Despande(MIT) Phase transitions in estimating low-rank matricesAbstract: Low-rank 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 information-theoretic 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
9-27-17 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 Euler-type hydrodynamics for one-dimensional 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.

10-23-17

*12:00-1: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 error-correcting 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,1-tau)] < 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 afore-mentioned 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.

10-25-17

*2:00-4:00pm*

 

Subhabrata Sen (Microsoft and MIT)

Noga Alon,(Tel Aviv University)

 

Subhabrata Sen, “Partitioning sparse random graphs: connections with mean-field spin glasses”

Abstract: The study of graph-partition problems such as Maxcut, max-bisection and min-bisection 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 cut-sizes on sparse Erd\ ̋{o}s-R\'{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.

11-1-17

*2:00-4:00pm*

 

Kay Kirkpatrick (Illinois)

and

Wei-Ming Wang (CNRS)

 

Kay Kirkpatrick, Quantum groups, Free Araki-Woods 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 Araki-Woods 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 Bose-Einstein condensation and work in progress.

Wei-Min Wang, Quasi-periodic solutions to nonlinear PDE’s

Abstract: We present a new approach to the existence of time quasi-periodic 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.

11-8-17 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.

11-10-17

*12pm SC 232*

 

Zhe Wang (NYU)

 

A Driven Tagged Particle in One-dimensional Simple Exclusion Process

Abstract: We study the long-time behavior of a driven tagged particle in a one-dimensional non-nearest- 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.

11-15-17

*4:00-5: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 multiple-network framework remains a relatively under-explored area. Individuals today interact with each other through numerous modalities including online social networks, telecommunications, face-to-face 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.

 

11-20-17

*Monday

12:00-1:00pm*

 Yue M. Lu

(Harvard)

Asymptotic Methods for High-Dimensional 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 high-dimensional 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 widely-used 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 mean-field limits to analyze nonconvex optimization algorithms for high-dimensional inference and learning. In these problems, asymptotic methods not only clarify some of the fascinating phenomena that emerge with high-dimensional data, they also lead to optimal designs that significantly outperform commonly used heuristic choices.
11-29-17 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 non-constructive 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 NAE-K-SAT problem, the problem of finding a largest submatrix of a random matrix, and a high-dimensional sparse linear regression problem in statistics.

Joint work with Wei-Kuo Chen, Quan Li, Dmitry Panchenko,  Mustazee Rahman, Madhu Sudan and Ilias Zadik.

12-6-17

*2:00-4:00pm*

Philippe Rigollet (MIT)

2-3 pm

&

Ankur Moitra (MIT)

3-4 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 Curie-Weiss 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 higher-order constraints.
Here we introduce a new approach for approximately counting and sampling in bounded degree systems. Our main result is an algorithm to approximately count the number of solutions to a CNF formula where the degree is exponential in the number of variables per clause. Our algorithm extends straightforwardly to approximate sampling, which shows that under Lovasz Local Lemma-like conditions, it is possible to generate a satisfying assignment approximately uniformly at random. In our setting, the solution space is not even connected and we introduce alternatives to the usual Markov chain paradigm.

12-14-17 TBD
Date Name Title
09-16-2015 Scott Aaronson, MIT BosonSampling and the Permanents of Gaussian Matrices
09-23-2015 Xin Sun, MIT Almost sure multi fractal spectrum of SLE
09-28-2015 Li-Cheng Tsai, Stanford KPZ equation limit of interacting particle systems
09-30-2015 Kyle Luh, Yale Random Matrices: l1 Concentration and Dictionary Learning with Few Samples
10-07-2015 Martin Zirnbauer, Cologne/Simons Center Bott periodicity and the “Periodic Table” of topological insulators and superconductors
10-14-2015 Benjamin Schweinhart, Harvard CMSA Universality Conjectures for Curvature Flow on Graphs
10-21-2015 Nicholas Cook, UCLA
10-28-2015 Vu-Lan Nguyen, Université Paris Diderot Variants of geometric RSK, geometric PNG and the multipoint distribution of the log-gamma polymer
11-04-2015 Vadim Gorin, MIT Largest eigenvalues in random matrix beta-ensembles: structures of the limit.
11-18-2015 Louis-Pierre Arguin, CUNY The maximum of the characteristic polynomial of random unitary matrices 
11-19-2015 Nicholas Zygouras, Univ. of Warwick From disorder relevance to the 2d Stochastic Heat Equation
11-25-2015 Thanksgiving No seminar
12-02-2015 Eero Saksman (Helsinki) The uniqueness of Gaussian multiplicative chaos revisited
12-04-2015 Guillaume Barraquand, Columbia Random walks in Beta random environment
01-27-2016 Louigi Addario-Berry, McGill Slowdown of the front for branching Brownian motion with decay of mass
02-03-2016 Antti Knowles, ETH Zurich An optimal rotational invariant estimator for general covariance matrices
02-10-2016 No Seminar this week
02-17-2016 Florent Bekerman, MIT Transport Methods and Universality for beta-matrix models
02-24-2016 Aukosh Jagannath, Courant Institute The Parisi variational problem
03-02-2016 No Seminar this week Two next week
03-09-2016 Adam Marcus, Princeton Polynomials and (finite) free probability
03-11-2016 Hao Shen, Columbia The Sine-Gordon stochastic PDE and regularity structures
03-16-2016 Spring Recess
03-23-2016 Zeev Rudnick, Tel-Aviv and IAS Quantum chaos, eigenvalue statistics and the Fibonacci sequence
03-30-2016 Nikolai Makarov, Caltech Random normal matrices with hard edge spectrum
04-06-2016 Timo Seppalainen, Wisconsin Variational formulas and Busemann functions for random paths in a random medium
04-11-2016 (Science Center 530) Milton D. Jara, IMPA Around the strong KPZ universality conjecture
04-20-2016 Mark Rudelson, Michigan Delocalization of eigenvectors of random matrices
04-27-2016 Marek Biskup, UCLA Local limit theory for extreme values of 2D Discrete Gaussian Free Field
05-04-2016 No Talk
05-11-2016 (2:30-3:30pm, Room G10) Laure Saint-Raymond, École Normale Supérieure Fluctuating dynamics for a 2D rarified gas of hard disks
06-01-2016 Jun Yin, University of Wisconsin Generalized Circular Law
06-08-2016 Paul Bourgade, NYU Extremes of random matrices and log-correlated fields

Related Posts