In 2004 J. Friedman wrote a ~100 page paper proving a conjecture of Alon which stated that random d-regular graphs are nearly optimal expanders. Since then, Friedman's result has been refined and generalized in several directions, perhaps most notably by Bordenave and Collins who in 2019 established strong convergence of independent permutation matrices (a massive generalization of Friedman's theorem), a result that led to groundbreaking results in spectral theory and geometry.  

In this talk I will present joint work with C. Chen, J. Tropp and R. van Handel, where we introduce a new proof technique that allows one to convert qualitative results in random matrix theory into quantitative ones. This technique yields a fundamentally new approach to the study of strong convergence which is more flexible and significantly simpler than the existing techniques. Concretely, we're able to obtain  (1) a remarkably short of Friedman's theorem (2) a quantitative version of the result of Bordenave and Collins (3) a proof of strong convergence for arbitrary stable representations of the symmetric group, which constitutes a substantial generalization of the result of Bordenave and Collins. 

Gaussian elimination with partial pivoting (GEPP) remains the most used dense linear solver. For a nxn matrix A, GEPP results in the factorization PA = LU where L and U are lower and upper triangular matrices and P is a permutation matrix. If A is a random matrix, then the associated permutation from the P factor is random. When is this a uniform permutation? How many disjoint cycles are in its cycle decomposition (which equivalently answers how many GEPP pivot movements are needed on A)? What is the longest increasing subsequence of this permutation? We will provide some statistical answers to these questions for select random matrix ensembles and transformations. For particular butterfly permutations, we will present full distributional descriptions for these particular statistics. Moreover, we introduce a random butterfly matrix ensemble that induces the Haar measure on the full 2-Sylow subgroup of the symmetric group on a set of size 2ⁿ.

We present a polynomial-time algorithm for online differentially private synthetic data generation. For a data stream within the hypercube [0,1]^d and an infinite time horizon, we develop an online algorithm that generates a differentially private synthetic dataset at each time t. This algorithm achieves a near-optimal accuracy bound in the 1-Wasserstein distance.

We present Fuk-Nagaev - type inequality for the sums of independent self-adjoint operators. This bound could be viewed as an extension of the well known “Matrix Bernstein” inequality to the case of operators with heavy-tailed norms. As a corollary, we deduce Rosenthal moment inequality that improves upon the previously known versions even in the scalar case. Finally, we will discuss applications of these bounds to the covariance estimation problem.