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 (non-psychic) 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 next-to-leading 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 2-449

  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 q-pushTASEP

  Abstract: The Kardar-Parisi-Zhang 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 non-integrable 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 "zero-temperature" models, a number of tools are available for this tail, but the situation is not as developed in positive temperature. We will discuss q-pushTASEP, an integrable interacting particle system and a positive temperature model, for which nevertheless a connection to the zero-temperature model of last passage percolation was recently discovered by Imamura-Mucciconi-Sasamoto. We use this to develop a new method to obtain bounds on the lower tail for the location of the right-most particle under step initial data.

• March 13

  TBA

  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 Branch-and-Bound (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 Branch-and-Bound, 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 2-361

  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 first-passage percolation models. We wish to study the geometry of d-dimensional 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 unit-norm 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 number-theoretic 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 t-PNG and stochastic six vertex models

  Abstract: The t-PNG model is a one-parameter 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 t-PNG 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 tools---both old and new---which 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 Harish-Chandra/Itzykson/Zuber integrals. We present one such result, focusing on extreme eigenvalues of deformed sample-covariance and Wigner random matrices. This confirms recent formulas of Maillard (2020) in the physics literature, precisely locating a transition point whose analogue in non-deformed models is not yet understood. Joint work with Jonathan Husson.