Monday, February 11th, 2019

9:30 am10:30 am
Speaker: Nima Anari (Stanford University)

I will discuss an extension and an application of the method of interlacing families, pioneered by Marcus, Spielman, and Srivastava, to a combinatorial conjecture of Goddyn on the existence of thin trees: Every k-edge-connected graph has a spanning tree which has at most O(1/k)-fraction of the edges in every cut.

Random spanning trees satisfy this conjecture within a factor of log(n)/log log(n). I will discuss how we can go beyond randomized rounding and prove the existences of trees that satisfy the conjecture within a factor of polyloglog(n). This requires extending the method of interlacing families to a setting where input matrices are chosen according to negatively dependent distributions, as opposed to an independent/product distribution.

I will also briefly discuss relations between the thin tree conjecture and the asymmetric traveling salesman problem.

Based on joint work with Shayan Oveis Gharan.

11:00 am12:00 pm
Speaker: Ryan O'Donnell (Carnegie Mellon University)

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).

1:30 pm2:15 pm
Speaker: Mohan Ravichandran (Mimar Sinan Fine Arts University)

We present some results on root bounds for convolutions of real stable polynomials and use these to get improved estimates in Kadison-Singer type problems. Combined with a simple trick that can yield control over both top and bottom eigenvalues, these can be used to prove some generalizations of results of Marcus, Spielman and Srivastava. Several problems will also be posed. This includes work done jointly with Jonathan Leake and Nikhil Srivastava.

2:45 pm3:30 pm
Speaker: Jonathan Leake (UC 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.

4:15 pm5:00 pm
Speaker: Nick Ryder (UC Berkeley)

When dealing with expected characteristic polynomials, the finite free convolutions (classically known as the Walsh and Grace-Szego Convolutions) play a central role. In a unpublished paper of Marcus, Speilman, Srivastava, they explore a random matrix interpretation of these polynomial convolutions and develop univariate methods for obtaining precise information on the movement of the max root under the convolution. Recently, some have explored related convolutions which we call the q−multiplicative and b−additive convolutions. In this talk we develop a general framework which transfers results from the multiplicative to the additive convolution, and use this to solve a recent conjecture of Branden, Shapiro, and Krasikov relating to root separation preservation under the b−additive convolution. This comes from joint work with Jonathan Leake.

Tuesday, February 12th, 2019

9:30 am10:30 am
Speaker: Octavio Arizmendi (Centro de Investigación en Matemáticas, CIMAT)

In this talk we will present the finite free cumulants introduced in joint work with Daniel Perales.  We will describe their properties as well as applications. Finally, we present further problems related to finite free convolution.

11:00 am12:00 pm
Speaker: Rasmus Kyng (Harvard University)

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.

1:30 pm2:15 pm
Speaker: Marcus Michelen (University of Pennsylvania)

For a discrete random variable, what information can we deduce from the roots of its probability generating function?  We consider a sequence of random variables X_n taking values between 0 and n, and let P_n(z) be its probability generating function. We show that if none of the complex zeros of the polynomials P_n(z) are contained in a neighborhood of 1 in the complex plane then a central limit theorem occurs, provided the variance of X_n isn't subpolynomial in n.  This result is sharp a sense that will be made precise, and thus disproves a conjecture of Pemantle and improves upon various results in the literature.  This immediately improves a multivariate central limit theorem of Ghosh, Liggett and Pemantle, and has ramifications for certain variables that arise in graph theory contexts.  Time permitting, we will describe other of our results connecting the location of the zeros of P_n(z) and the distribution of the random variables X_n.  This is based on joint work with Julian Sahasrabudhe.

2:30 pm3:30 pm
Speaker: Nikhil Bansal (Eindhoven University of Technology)

Combinatorial discrepancy deals with the following question. Given a collection of vectors or matrices A_i, determine -1 or +1 signs s_i such that some suitable norm of the signed sum  \sum_i s_i A_i  is as small as possible. I will briefly survey some recent techniques that have been developed to address such problems and describe some open problems in the area.

Wednesday, February 13th, 2019

9:00 am10:00 am
Speaker: June Huh (Princeton University)

I will give a gentle overview of my work with Petter Brändén on Lorentzian polynomials from a tropical point of view. No specific background will be needed to enjoy the talk.

10:15 am11:15 am
Speaker: Cynthia Vinzant (North Carolina State University)

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.

11:45 am12:45 pm
Speaker: Tali Kaufman (Bar-Ilan University)

High dimensional random walks on high dimensional expanders are being studied extensively recently and have found various applications. In this talk, I will describe a new object called a Multi-Layer-Sampler that emerges from high dimensional random walks. This notion extends the well studied notion of samplers in a strong sense. I will discuss the usefulness of multi-layer-samplers for robust testing of codes and hint on other applications of this object.

2:00 pm2:45 pm
Speaker: Izhar Oppenheim (Ben Gurion University)

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.

3:15 pm4:15 pm
Speaker: Federico Ardila (San Francisco State University)

In recent years, the geometric roots of matroid theory have grown much deeper, bearing many new fruits. This talk will survey some recent successes. We will discuss three geometric models of matroids at the intersection of combinatorics, algebra, and geometry. Each has led to the development of intriguing combinatorics and to the solution of long-standing conjectures on graph and matroid inequalities.

Thursday, February 14th, 2019

9:30 am10:30 am
Speaker: Kuikui Liu (University of Washington)

We observe a correspondence between analytic properties of multi-affine homogeneous polynomials, and combinatorial and spectral properties of "high-dimensional expanders", which are extensions of usual expander graphs to hypergraphs. We show that complete log-concavity corresponds to strong expansion properties of the associated hypergraphs. Implications include new mixing time bounds for combinatorially defined Markov chains. Algorithmic applications to approximate counting and sampling problems will be discussed.

11:00 am12:00 pm
Speaker: Karim Adiprasito (Hebrew University of Jerusalem)

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.

1:30 pm2:15 pm
Speaker: Yuval Peled (NYU Courant Institute)

Over thirty years ago, Kalai proved a beautiful d-dimensional analog of Cayley's formula for the number of n-vertex trees. Namely, he enumerated d-dimensional hypertrees weighted by the squared size of their (d-1)-dimensional homology group. This, however, does not answer the more basic problem of unweighted enumeration of d-hypertrees which is our concern here. We analyse a random-greedy construction of d-hypertrees and show it significantly improves the previous known lower bound for their number. Second, we introduce a model of random 1-out d-dimensional complexes, and show that it has a negligible d-dimensional homology with high probability.

Joint work with Nati Linial.

2:45 pm3:30 pm
Speaker: Benoît Collins (Kyoto University)

Given a non-commutative polynomial $P$ in non-commuting unitary variables and their inverse, we consider a sequence of random matrices $P_n$ in the $n\times n$ matrices obtained by replacing the unitary variables by random i.i.d permutations on n points (viewed as unitary $n\times n$ matrices). Free probability predicts, with high probability in the large dimension limit, the behavior of most singular values of $P_n$. We will show that this prediction extends to the second largest singular value of $P_n$, i.e. that it converges with high probability to the operator norm of $P$ in the reduced C*-algebra of the free group. Time allowing, we will discuss some points of the proof (requiring the development of a non-commutative version of non-backtracking operator theory) and some applications to random graph theory. This talk is based on joint work with Charles Bordenave (CNRS).

Friday, February 15th, 2019

9:30 am10:30 am
Speaker: Peter Sarnak (IAS)

We examine a basic problem of what can be determined efficiently about the eigenvalues of a matrix in O(2n) given the traces of its first k (<n ) powers. We explain how this can be used to compute root numbers and count zeros of L functions, in sub exponential time (in the conductor). Joint work with M. Rubinstein.

11:00 am12:00 pm
Speaker: Rafael Oliveira (University of Toronto)

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.

1:30 pm2:15 pm
Speaker: Amin Saberi (Stanford University)

We study the problem of allocating m items to n agents subject to maximizing the Nash Social Welfare (NSW) objective. We write a novel convex programming relaxation for this problem, and we show that a simple randomized rounding algorithm gives a 1/e approximation factor of the objective.  Our main technical contribution is an extension of Gurvits's lower bound on the coefficient of the square-free monomial of a degree m-homogeneous stable polynomial on m variables to all homogeneous polynomials. We use this extension to analyze the expected welfare of the allocation returned by our randomized rounding algorithm.

Joint work with Nima Anari, Shayan Oveis Gharan, and Mohit Singh.

2:45 pm3:30 pm
Speaker: Olga Holtz (UC Berkeley)

Zonotopal algebra studies special multivariate polynomials that encode, simultaneously, combinatorial properties of linear matroids, analytic properties of box splines, and various graph statistics. After a brief introduction to the main constructions in that area, I will focus on their intriguing potential uses in analysis and combinatorics.