Seminars and Colloquia by Series

Small Ball Probability for the Smallest Singular Value of a Complex Random Matrix

Series
High Dimensional Seminar
Time
Wednesday, February 19, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michail SarantisGeorgiaTech

Let $N_n$ be an $n\times n$ matrix whose entries are i.i.d. copies of a random variable $\zeta=\xi+i\xi'$, where $\xi,\xi'$ are i.i.d., mean zero, variance one, subgaussian random variables. We will present a result of Luh, according to which the probability that $N_n$ has a real eigenvalue is exponentially small in $n$. An interesting part of the proof is a small ball probability estimate for the smallest singular value of a complex perturbation $M_n=M+N_n$ of the original matrix.

Improved bounds for Hadwiger covering problem via the thin shell estimates

Series
High Dimensional Seminar
Time
Wednesday, January 29, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Speaker
Han HuangGeorgia Tech

Let $K$ be a n dimensional convex body with of volume $1$. and barycenter of $K$ is the origin.  It is known that $|K \cap -K|>2^{-n}$.  Via thin shell estimate by Lee-Vempala (earlier versions were done by Guedon-Milman, Fleury, Klartag), we improve the bound by a sub-exponential factor.  Furthermore, we can improve  the Hadwiger’s Conjecture in the non-symmetric case by a sub-exponential factor.  This is a joint work with Boaz A. Slomka, Tomasz Tkocz, and Beatrice-Helen Vritsiou. 

On the L_p-Brunn-Minkowski inequality for measures

Series
High Dimensional Seminar
Time
Wednesday, January 22, 2020 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Galyna LivshytsGeorgia Tech

The first part of this pair of talks will be given at the Analysis seminar right before; attending it is not necessary, as all the background will be given in this lecture as well, and the talks will be sufficiently independent of each other.

I will discuss the L_p-Brunn-Minkowski inequality for log-concave measures, explain ‘’Bochner’s method’’ approach to this problem and state and prove several new results. This falls into a general framework of isoperimetric type inequalities in high-dimensional euclidean spaces. Joint with Hosle and Kolesnikov.

A new proof of the Caffarelli contraction theorem

Series
High Dimensional Seminar
Time
Wednesday, December 4, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Max FathiMathematics Institute, Toulouse, France

The Caffarelli contraction theorem states that the Brenier map sending the
Gaussian measure onto a uniformly log-concave probability measure is
lipschitz. In this talk, I will present a new proof, using entropic
regularization and a variational characterization of lipschitz transport
maps. Based on joint work with Nathael Gozlan and Maxime Prod'homme.

The condition number of square random matrices

Series
High Dimensional Seminar
Time
Wednesday, November 20, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Michail SarantisGeorgiaTech

The condition number of a matrix A is the quantity κ(A) = smax(A)/smin(A), where smax(A), smin(A) are the largest and smallest singular values of A, respectively. Let A be a random n × n matrix with i.i.d, mean zero, unit variance, subgaussian entries. We will discuss a result by Litvak, Tikhomirov and Tomczak-Jaegermann which states that, in this setting, the condition number satisfies the small ball probability estimate

P{κ(A) ≤ n/t} ≤ 2 exp(−ct^2), t ≥ 1, where c > 0 is a constant depending only on the subgaussian moment.

Hard-core models on triangular and square lattices

Series
High Dimensional Seminar
Time
Wednesday, November 13, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Izabella StuhlPenn State

One of the outstanding open problems of statistical mechanics is about the hard-core model which is a popular topic in mathematical physics and has applications in a number of other disciplines. Namely, do non-overlapping hard disks of the same diameter in the plane admit a unique Gibbs measure at high density? It seems natural to approach this question by requiring the centers to lie in a fine lattice; equivalently, we may fix the lattice, but let the Euclidean diameter D of the hard disks tend to infinity. In two dimensions, it can be a unit triangular lattice A_2 or a unit square lattice Z^2. The randomness is generated by Gibbs/DLR measures with a large value of fugacity which corresponds to a high density. We analyze the structure of high-density hard-core Gibbs measures via the Pirogov-Sinai theory. The first step is to identify periodic ground states, i.e., maximal-density disk configurations which cannot be locally `improved'. A key finding is that only certain `dominant' ground states, which we determine, generate nearby Gibbs measures. Another important ingredient is the Peierls bound separating ground states from other admissible configurations. In particular, number-theoretic properties of the exclusion diameter D turn out to be important. Answers are provided in terms of Eisenstein primes for A_2 and norm equations in the cyclotomic ring Z[ζ] for Z^2, where ζ is the primitive 12th root of unity. Unlike most models in statistical physics, we find non-universality: the number of high-density hard-core Gibbs measures grows indefinitely with D but
non-monotonically. In Z^2 we also analyze the phenomenon of 'sliding' and show it is rare.
This is a joint work with A. Mazel and Y. Suhov.

Smoothed analysis of the least singular value without inverse Littlewood--Offord theory

Series
High Dimensional Seminar
Time
Wednesday, November 6, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Speaker
Vishesh JainMIT

We will discuss a novel approach to obtaining non-asymptotic estimates on the lower tail of the least singular value of an $n \times n$ random matrix $M_{n} := M + N_{n}$, where $M$ is a fixed matrix with operator norm at most $O(\exp(n^{c}))$ and $N_n$ is a random matrix, each of whose entries is an independent copy of a random variable with mean 0 and variance 1. This has been previously considered in a series of works by Tao and Vu, and our results improve upon theirs in two ways: 

(i) We are able to deal with $\|M\| = O(\exp(n^{c}))$ whereas previous work was applicable for $\|M\| = O(\poly(n))$. 

(ii) Even for $\|M\| = O(poly(n))$, we are able to extract more refined information – for instance, our results show that for such $M$, the probability that $M_n$ is singular is $O(exp(-n^{c}))$, whereas even in the case when $N_n$ is an i.i.d. Bernoulli matrix, the results of Tao and Vu only give inverse polynomial singularity probability.  

 

The Ehrhard-Borell inequality and hypoelliptic diffusions

Series
High Dimensional Seminar
Time
Wednesday, October 30, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Yair ShenfeldPrinceton University

The Ehrhard-Borell inequality stands at the top of the pyramid of Gaussian inequalities. It is a powerful and delicate statement about the convexity of the Gaussian measure. In this talk I will discuss the inequality and its beautiful proof by Borell. The delicate nature of the inequality however makes the characterization of the equality cases difficult and they were left unknown. I will explain how we solved this problem. Joint work with Ramon van Handel.

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Series
High Dimensional Seminar
Time
Wednesday, October 23, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Andre WibisonoGeorgia Tech

Sampling is a fundamental algorithmic task. Many modern applications require sampling from complicated probability distributions in high-dimensional spaces. While the setting of logconcave target distribution is well-studied, it is important to understand sampling beyond the logconcavity assumption. We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution on R^n under isoperimetry conditions. We show a convergence guarantee in Kullback-Leibler (KL) divergence assuming the target distribution satisfies log-Sobolev inequality and the log density has bounded Hessian. Notably, we do not assume convexity or bounds on higher derivatives. We also show convergence guarantees in Rényi divergence assuming the limit of ULA satisfies either log-Sobolev or Poincaré inequality. Joint work with Santosh Vempala (arXiv:1903.08568).

Regularity Decompositions for Sparse Pseudorandom Graphs

Series
High Dimensional Seminar
Time
Wednesday, October 16, 2019 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Gregory M BodwinGeorgia Tech

 A powerful method for analyzing graphs is to first apply regularity lemmas, which roughly state that one can partition the graph into a few parts so that it looks mostly random between the parts, and then apply probabilistic tools from there.  The drawback of this approach is that it only works in general when the input graph is very dense: standard regularity lemmas are trivial already for n-node graphs on "only" <= n^{1.99} edges.

In this work we prove extensions of several standard regularity lemmas to sparse graphs, which are nontrivial so long as the graph spectrum is not too far from that of a random graph.  We then apply our notion of "spectral pseudorandomness" to port several notable regularity-based results in combinatorics and theoretical computer science down to sparser graphs.

 

Joint work with Santosh Vempala.

 

Pages