Let X be the infinite graph partially pictured below, the "free product graph" C_4 * C_4 * C_4.  Let FinQuo(X) be the set of all finite graphs G that covered by X (i.e., that 'locally resemble' X; i.e., that consist of C_4's joined 3-to-a-vertex).  A known Alon-Boppana-type theorem implies that every G in FinQuo(X) has second eigenvalue at least sqrt(5sqrt(5)+11) - o(1), where that magic number is the spectral radius of X.  We may then ask the "Ramanujan question": are there infinitely many G in FinQuo(X) with second eigenvalue at most sqrt(5sqrt(5)+11)?  When X is the infinite d-regular tree, this is the well known Ramanujan graph problem resolved by Marcus, Spielman, and Srivastava [MSS].

We show a positive answer to the problem for a wide variety of infinite X (not necessarily trees).  Techniques involve a new infinite graph product, a new graph polynomial (generalizing the matching polynomial), "freelike walks", Heaps of Pieces, and of course [MSS]'s Interlacing Polynomials Method.

Joint work with Sidhanth Mohanty (CMU/Berkeley).

Since the celebrated resolution of Kadison-Singer (via the Paving Conjecture) by Marcus, Spielman, and Srivastava, much study has been devoted to further understanding and generalizing the techniques of their proof. Specifically, their barrier method was crucial to achieving the required polynomial root bounds on the finite free convolution. But unfortunately this method required individual analysis for each usage, and the existence of a larger encapsulating framework is an important open question. In this talk, we discuss steps toward such a framework by generalizing their root bound to all differential operators. We further conjecture a large class of root bounds, the resolution of which would require for more robust techniques. We further give an important counterexample to a very natural multivariate version of their bound, which if true would have implied tight bounds for the Paving Conjecture. This talk is based on joint work with Nick Ryder, via a paper of the same title.

Strongly Rayleigh distributions are a class of negatively dependent distributions of binary-valued random variables (Borcea-Branden-Liggett 2009). A probability distribution over {0,1}^n is Strongly Rayleigh if its associated generating polynomial is real stable. If the distribution has exactly k entries that are 1 in every outcome, it is said to be k-homogeneous. We prove a matrix Chernoff bound that shows concentration of sums of PSD matrices scaled by coefficients that have a Strongly Rayleigh, k-homogenous distribution.

Because random spanning trees are k-homogenous Strongly Rayleigh, we can use our matrix Chernoff bound to show new results for approximation of graph Laplacians by sampling sums of random spanning trees. We show that O(epsilon^-2 log^2 n) spanning trees give a (1+eps)-spectral sparsifier of a graph Laplacian with high probability, and show from a simple lower bound that at least epsilon^-2 log n spanning trees are necessary.

Stability is a multivariate generalization for real-rootedness in univariate polynomials. Within the past ten years, the theory of stable polynomials has contributed to breakthroughs in combinatorics, convex optimization, and operator theory. I will introduce a generalization of stability, called complete log-concavity, that satisfies many of the same desirable properties. These polynomials were inspired by recent work of Adiprasito, Huh, and Katz on combinatorial Hodge theory, but can be defined and understood in elementary terms. I will discuss the beautiful geometry underlying these polynomials and discuss some applications to approximate counting problems in matroid theory. This is based on joint work with Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.

Given a simplicial complex X, the k-dimensional random walk on it is the random walk between k-faces of X through (k+1)-faces. We show that under suitable assumptions on the spectral gaps of the links of the X, we can bound (or even determine up to a small error) the rate of convergence of the random walk for a given function on k-faces.

This result fits into a larger framework, in which we think about a simplicial complex with large spectral gaps in the links as a (spectral) high dimensional analogue of an expander graph.

This talk is based on a joint work with Tali Kaufman.

We discuss probablistic techniques used towards the higher-dimensional crossing lemma, and the more basic question of how many triangles a simplicial complex in R^4 can have. We then introduce an algebraic formulation of this question, and improve on results in algebraic geometry to give the tight answer.

In this talk, we will discuss two examples of scaling problems (matrix scaling and operator scaling), which have recently been used to solve problems in a wide variety of areas, ranging from non-commutative algebra and invariant theory to functional analysis. These scaling problems have very simple and deterministic algorithms which give (1+epslion) multiplicative approximation to compute Gurvits' capacity, as well as the Brascamp-Lieb constant (whenever the latter is finite).

This talk is based on joint work with Ankit Garg, Leonid Gurvits and Avi Wigderson.