Spring 2023
Monday 4.15  5.15 pm
Room 2147
Scheduled virtual talks will be held on Zoom, Monday 4:155:15 pm.
A link to a Zoom classroom will appear here!!
Schedule

February 6
Xuan Wu (University of Chicago)
TBA
Abstract: TBA.

February 13
Eveliina Peltola (University of Bonn)
TBA
Abstract: TBA.

February 20
President's Day

February 27
Andrea Ottolini (University of Washington)
Some math behind the Zener cards
Abstract: The Zener cards are a deck of nm cards where each of n symbols is depicted on exactly m cards. The following experiment (n=m=5) has been used since the early ‘30s to test for extrasensory perceptions: the alleged telepath tries to guess cards one at a time, receiving some feedback after each attempt, until there are no cards left. The total number of correct guesses can be thus interpreted as a measure of their psychic powers. A very first step in the analysis of such experiments is to determine the optimal (nonpsychic) expected score S_{n,m}. After an overview of the problem, I will focus on joint work with Steinerberger on the complete feedback case, where we determine the leading and nexttoleading order for S_{n,m} in a wide range of regimes. In particular, this includes the case n=m, answersing a conjecture of Diaconis.

March 6
2:00 pm, Room 2449
Oren Louidor (Technion)
Tightness for the Cover Time on Wired Planar Domains
Abstract: We consider a continuous time simple random walk on a subset of the square lattice with wired boundary conditions: The walk transitions at unit edge rate on the graph obtained from the lattice closure of the subset by contracting the boundary into one vertex. We study the cover time of such walk, namely the time it takes for the walk to visit all vertices in the graph. Taking a sequence of subsets obtained as scaled lattice versions of a nice planar domain, we show that the square root of the cover time normalized by the size of the subset, is tight around $\frac{1}{\sqrt{\pi}} \log N  \frac{1}{4 \sqrt{\pi}} \log \log N$, where $N$ is the scale parameter. The proof is based on comparison with the extremal landscape of the discrete Gaussian free field. Joint work with Marek Biskup and Santiago Saglietti.

March 6
Milind Hegde (Columbia)
The lower tail of qpushTASEP
Abstract: The KardarParisiZhang class is a broad class of models which are believed to exhibit universal behaviors. Currently, detailed information is known essentially only for a handful of models with algebraic connections, known as integrable models. In the past decade, however, some progress has been made in studying some nonintegrable settings, where a crucial input has been quantitative bounds on upper and lower tails of the relevant observable in related integrable settings. Of the two, the lower tail is typically more challenging. In the context of "zerotemperature" models, a number of tools are available for this tail, but the situation is not as developed in positive temperature. We will discuss qpushTASEP, an integrable interacting particle system and a positive temperature model, for which nevertheless a connection to the zerotemperature model of last passage percolation was recently discovered by ImamuraMucciconiSasamoto. We use this to develop a new method to obtain bounds on the lower tail for the location of the rightmost particle under step initial data.

March 13
TBA
Abstract: TBA.

March 20
Patrick Shafto (Rutgers, Newark Campus)
TBA
Abstract: TBA.

March 27
Spring Break

April 3
Aukosh Jagannath (University of Waterloo)
TBA
Abstract: TBA.

April 10
Daniel Dadush (CWI)
Integrality Gaps for Random Integer Programs via Discrepancy
Abstract: We prove new bounds on the additive gap between the value of a random integer program max c^T x, Ax≤b, x∈{0,1}^n with m constraints and that of its linear programming relaxation for a wide range of distributions on (A,b,c) . We are motivated by the work of Dey, Dubey, and Molinaro (SODA '21), who gave a framework for relating the size of BranchandBound (B&B) trees to additive integrality gaps.
Dyer and Frieze (MOR '89) and Borst et al. (Mathematical Programming '22), respectively, showed that for certain random packing and Gaussian IPs, where the entries of A,c are independently distributed according to either the uniform distribution on [0,1] or the Gaussian distribution N(0,1), the integrality gap is bounded by O_m(log^2(n)/n) with probability at least 1−1/n−e{Omega(m)}. In this paper, we generalize these results to the case where the entries of A are uniformly distributed on an integer interval (e.g., entries in {−1,0,1}), and where the columns of A are distributed according to an isotropic logconcave distribution. Second, we substantially improve the success probability to 1−1/poly(n), compared to constant probability in prior works (depending on m). Leveraging the connection to BranchandBound, our gap results imply that for these IPs B&B trees have size n^poly(m) with high probability (i.e., polynomial for fixed m), which significantly extends the class of IPs for which B&B is known to be polynomial.
Our main technical contribution is a new linear discrepancy theorem for random matrices. Our theorem gives general conditions under which a target vector is equal to or very close to a {0,1} combination of the columns of a random matrix A. The proof uses a Fourier analytic approach, building on work of Hoberg and Rothvoss (SODA '19) and Franks and Saks (RSA '20)

April 10
11:00 am, Room 2361
Ron Peled (Tel Aviv University, IAS, and Princeton University)
Minimal Surfaces in Random Environment
Abstract: A minimal surface in a random environment (MSRE) is a surface which minimizes the sum of its elastic energy and its environment potential energy, subject to prescribed boundary values. Apart from their intrinsic interest, such surfaces are further motivated by connections with disordered spin systems and firstpassage percolation models. We wish to study the geometry of ddimensional minimal surfaces in a (d+n)dimensional random environment. Specializing to a model that we term harmonic MSRE, we rigorously establish bounds on the geometric and energetic fluctuations of the minimal surface, as well as a scaling relation that ties together these two types of fluctuations. Our results agree with predictions from the physics literature.
Joint work with Barbara Dembin, Dor Elboim and Daniel Hadas.

April 17
Patriot's Day

April 24
Tim Kunisky (Yale)
Spectral limit theorems for submatrices and products of projections
Abstract: I will present broadly applicable limit theorems for the empirical spectral distributions of products of projection matrices that are in sufficiently "general position," proved using the tools of free probability. As special cases, these results describe the singular values of random subsets of unitnorm tight frames and of random rectangular submatrices of unitary matrices. I will show how, in those settings, these limit theorems prove empirical observations and conjectures made in the signal processing and combinatorics communities and give an intuitive free probability explanation for the universality phenomena observed in those contexts.
I will also discuss some deterministic settings where the same results apply. In particular, I will present surprising deterministic examples of asymptotic freeness exhibited by matrices related to the numbertheoretic Paley graph, and will explain the relevance of this to problems in Ramsey theory and analytic number theory.
Finally, time permitting, I will present initial results on limit theorems for the extreme eigenvalues of such matrices, explain their significance to the above applications, and discuss the additional combinatorial and analytic challenges of proving such results.

May 1
Hindy Drillick (Columbia)
Using colored models to prove strong laws of large numbers for the tPNG and stochastic six vertex models
Abstract: The tPNG model is a oneparameter deformation of the polynuclear growth model that was recently introduced by Aggarwal, Borodin, and Wheeler, who studied its fluctuations using integrable probability methods. In this talk, we will discuss how to use techniques from interacting particle systems to prove a strong law of large numbers for this model. To do so, we will introduce a new colored version of the model that allows us to apply Liggett’s subadditive ergodic theorem to obtain the hydrodynamic limit. The tPNG model also has a close connection to the stochastic six vertex model. We will discuss this connection and explain how we can prove similar results for the stochastic six vertex model. This talk is based on joint work with Yier Lin.

May 8
Marcus Michelen (UIC)
Singularity and the least singular value of random symmetric matrices
Abstract: Consider the random symmetric n x n matrix whose entries on and above the diagonal are independent and uniformly chosen from {1,1}. How often is this matrix singular? A moment's thought reveals that if two rows or columns are equal then the matrix is singular, so the singularity probability is bounded below by 2^{n(1 + o(1))}. Proving any sort of upper bound on the singularity probability turns out to be difficult, with results coming slowly over the past two decades. I'll discuss work which shows the first exponential upper bound on this probability as well as extensions to more quantitative notions of invertibility. Along the way, I'll describe some toolsboth old and newwhich are powerful and (hopefully) interesting in their own right. This talk is based on joint work with Marcelo Campos, Matthew Jenssen, and Julian Sahasrabudhe.

May 15
Ben McKenna (Harvard)
Large deviations for the top eigenvalue of deformed random matrices
Abstract: In recent years, the few classical results in large deviations for random matrices have been complemented by a variety of new ones, in both the math and physics literatures, whose proofs leverage connections with HarishChandra/Itzykson/Zuber integrals. We present one such result, focusing on extreme eigenvalues of deformed samplecovariance and Wigner random matrices. This confirms recent formulas of Maillard (2020) in the physics literature, precisely locating a transition point whose analogue in nondeformed models is not yet understood. Joint work with Jonathan Husson.