Mar 09, 2015
Monday

09:15 AM  09:30 AM


Welcome

 Location
 MSRI: Simons Auditorium
 Video


 Abstract
 
 Supplements



09:30 AM  10:30 AM


Hyperbolic polynomials, Strong Rayleigh matroids and the MarcusSpielmanSrivastava theorem
Petter Branden (Royal Institute of Technology (KTH))

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
: Hyperbolic polynomials are generalizations of determinantal polynomials, and hyperbolicity cones are generalizations of the cone of positive semidefinite matrices.
I will show how the recent MarcusSpielmanSrivastava theorem (implying the KadisonSinger conjecture) may be generalized to hyperbolic polynomials, and point to some potential applications in combinatorics.
The generalized Lax conjecture asserts that hyperbolicity cones are linear sections of the cone of positive semidefinite matrices. Recently the speaker disproved an algebraic strengthening of this conjecture by using Ingleton's inequality for matroids that are representable over some field. Kinser recently introduced an infinite family of inequalities that generalize Ingleton's inequality. For each Kinser inequality we construct a Strong Rayleigh matroid which fails to satisfy the inequality. This produces an infinite family of hyperbolic polynomials such that no power of a polynomial in the family is a determinantal polynomial.
The second part of this talk is based on joint work with Nima Amini.
 Supplements



10:30 AM  11:00 AM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



11:00 AM  12:00 PM


Introduction to Interlacing Polynomials, Barrier Functions, and KadisonSinger
Daniel Spielman (Yale University)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
I will introduce the method of interlacing polynomials and analysis by barrier functions through a proof of the Restricted Inevitability Principle. I will state Weaver's discrepancytheoretic version of the KadisonSinger Conjecture, and sketch the role that hyperbolic polynomials play in its proof. If time permits, I will connect these with Ramanujan graphs and the matchings polynomials of graphs.
 Supplements



12:00 PM  02:00 PM


Lunch

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



02:00 PM  03:00 PM


Determinants, Hyperbolicity, and Interlacing
Cynthia Vinzant (North Carolina State University)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
On the space of real symmetric matrices, the determinant is hyperbolic with respect to the cone of positive definite matrices. As a consequence, the determinant of a matrix of linear forms that is positive definite at some point is a hyperbolic polynomial. A celebrated theorem of Helton and Vinnikov states that any hyperbolic polynomial in three variables has such a determinantal representation. In more variables, this is no longer the case. During this talk, we will examine hyperbolic polynomials that do and do not have definite determinantal representations. Interlacing polynomials will play an interesting role in this story and form a convex cone in their own right.
 Supplements



03:00 PM  03:30 PM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



03:30 PM  04:30 PM


An overview of the Matching Polynomial
Chris Godsil (University of Waterloo)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
A $k$matching in a graph $X$ is a set of $k$ vertexdisjoint edges. If we denote
the number of $k$matchings in a graph $G$ by $p(G,k)$ and $V(G)=n$, then its matching polynomial is
\[
\mu(G,t) = \sum_k (1)^k p(G,k) t^{n2k}.
\]
It is thus a form of generating function, with fudge factors inserted to make our work easier.
Matchings are a central topic in graph theory, but nonetheless this polynomial appeared in Physics and in Chemistry, before becoming an object of interest to graph theorists. If the graph $G$ is a forest, its matching polynomial coincides with the characteristic polynomial of the adjacency matrix of $G$, and considering the analogies between these two polynomials has proved very fruitful. In my talk I will present some of the history of the matching polynomial, along with interesting parts of its theory.
 Supplements




Mar 10, 2015
Tuesday

09:30 AM  10:30 AM


Laws of noncommutative polynomials in $n$tuples of free variables
Dimitri Shlyakhtenko (University of California, Los Angeles)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
 
 Supplements



10:30 AM  11:00 AM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



11:00 AM  12:00 PM


Free probability, random matrices and transport maps
Alice Guionnet (École Normale Supérieure de Lyon)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
We will discuss transport maps techniques to construct isomorphisms of C^* algebras and study the local fluctuations of the eigenvalues of polynomials in several GUE matrices.
 Supplements



12:00 PM  02:00 PM


Lunch

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



02:00 PM  03:00 PM


Polynomial convolutions and connections to free probability
Adam Marcus (Yale University)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
 
 Supplements



03:00 PM  03:30 PM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



03:30 PM  04:30 PM


Ramanujan graphs from finite free convolutions.
Nikhil Srivastava (University of California, Berkeley)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
 
 Supplements



04:30 PM  06:20 PM


Reception

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements




Mar 11, 2015
Wednesday

09:30 AM  10:30 AM


Towards Constructing Expanders via Lifts: Hopes and Limitations
Alexandra Kolla (University of Illinois at UrbanaChampaign)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
In this talk, I will examine the spectrum of random klifts of dregular graphs. We show that, for random shift klifts (which includes 2lifts), if all the nontrivial eigenvalues of the base graph G are at most \lambda in absolute value, then with high probability depending only on the number n of nodes of G (and not on k), if k is *small enough*, the absolute value of every nontrivial eigenvalue of the lift is at most O(\lambda). While previous results on random lifts were asymptotically true with high probability in the degree of the lift k, our result is the first upperbound on spectra of lifts for bounded k. In particular, it implies that a typical small lift of a Ramanujan graph is almost Ramanujan. I will also discuss some impossibility results for large k, which, as one consequence, imply that there is no hope of constructing large Ramanujan graphs from abelian klifts. based on joint and ongoing work with Naman Agarwal Karthik Chandrasekaran and Vivek Madan
 Supplements



10:30 AM  11:00 AM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



11:00 AM  12:00 PM


Expanders and box spaces
Alain Valette (Université de Neuchâtel)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
Box spaces of finitely generated groups are disjoint union of Cayley graphs of finite quotients associated with some decreasing sequence of finite index normal subgroups of the given group. In 1973 Margulis gave the first explicit construction of expanders by proving that box spaces of property (T) groups are expanders. In 2012 Mendel and Naor showed the existence of two expanders $F_1,F_2$ such that $F_1$ does not coarsely embed into $F_2$. In February 2015, Hume constructed a continuum of expanders with unbounded girth, not coarsely embedding into one another. In joint work with Ana Khukhro, we construct countably many expanders with bounded girth, as box spaces of groups with property $(\tau)$, and prove that they do not coarsely embed into one another.
 Supplements




Mar 12, 2015
Thursday

09:30 AM  10:30 AM


Commutators in L(X) for some Banach spaces X
William Johnson (Texas A & M University)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
I will survey what is known about classifying the commutators in the space of bounded linear operators L(X), X a Banach space.
 Supplements



10:30 AM  11:00 AM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



11:00 AM  12:00 PM


A quantitative version of the commutator theorem for zero trace matrices
Gideon Schechtman (Weizmann Institute of Science)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
 
 Supplements


12:00 PM  02:00 PM


Lunch

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



02:00 PM  03:00 PM


Paving over arbitrary MASAs in von Neumann algebras
Stefaan Vaes (Katholieke Universiteit Leuven)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
I will present some recent work with Stefaan Vaes, in which we consider a paving property for a MASA $A$
in a von Neumann algebra $M$, that we call \emph{\sopaving}, involving approximation in the {\so}topology, rather
than in norm (as in classical KadisonSinger paving).
If $A$ is the range of a normal conditional expectation, then {\so}paving is equivalent to
norm paving in the ultrapower inclusion $A^\omega\subset M^\omega$.
We conjecture that any MASA in any von Neumann algebra satisfies {\so}paving.
We use recent work of MarcusSpielmanSrivastava to check this for all MASAs in $\mathcal B(\ell^2\mathbb N)$, all Cartan subalgebras in amenable von Neumann
algebras and in group measure space II$_1$ factors arising from profinite actions.
By work of mine from 2013, the conjecture also holds true for singular MASAs in II$_1$ factors, and we obtain an improved paving size
$C\varepsilon^{2}$, which we show to be sharp.
 Supplements



03:00 PM  03:30 PM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



03:30 PM  04:30 PM


A survey of discrepancy theory
Nicholas Harvey (University of British Columbia)

 Location
 MSRI: Simons Auditorium
 Video


 Abstract
Discrepancy theory has been an important research area in combinatorics and geometry for several decades. The MarcusSpielmanSrivastava theorem can be viewed as a "spectral" discrepancy theorem. In this talk we will survey some of the classical results and recent progress in this area, as well as mentioning some open questions.
 Supplements




Mar 13, 2015
Friday

09:30 AM  10:30 AM


Hyperbolic Polynomials in Optimization
Osman Guler (University of Maryland Baltimore County)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
During the last two decades, hyperbolic polynomials have been influential in significant advances in diverse fields of mathematics.
In this talk, I will touch focus their role in optimization and convex analysis.
 Supplements



10:30 AM  11:00 AM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



11:00 AM  12:00 PM


EffectiveResistanceReducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Shayan Oveis Gharan (University of Washington)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
Given a kedgeconnected graph G=(V,E), a spanning tree T is athin w.r.t. G, if for any S⊂V, T(S,V−S)≤a.E(S,V−S). The thin tree conjecture asserts that for a sufficiently large k (independent of size of G) every kedgeconnected graph has a 1/2thin tree. This conjecture can be seen as an L1 analogous of KS_r, for r=k, restricted to graphs. It is intimately related to designing approximation algorithms for Asymmetric Traveling Salesman Problem (ATSP).
In this work, we show that any kconnected graph has a polyloglog(n)/kthin spanning tree. This implies that the integrality gap of the natural LP relaxation of ATSP is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). This is the first significant improvement over the classical O~(log n) approximation factor for ATSP. Our proof builds on the method of interlacing polynomials of Marcus, Spielman and Srivastava and employs several tools from spectral graph theory and high dimensional geometry.
Based on a joint work with Nima Anari.
 Supplements



12:00 PM  02:00 PM


Lunch

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



02:00 PM  03:00 PM


Approximating the covariance matrix by the empirical covariance matrices; nonlimiting random matrix approach
Nicole TomczakJaegermann (University of Alberta)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
 
 Supplements



03:00 PM  03:30 PM


Tea

 Location
 MSRI: Atrium
 Video


 Abstract
 
 Supplements



03:30 PM  04:30 PM


Hyperbolicity and determinantal representations for highercodimensional subvarieties
Victor Vinnikov (Ben Gurion University of the Negev)

 Location
 MSRI: Simons Auditorium
 Video

 Abstract
Let $X $ be a real subvariety of codimension $\ell$ in the complex projective space ${\mathbb P}^d$.
We say that $X$ is hyperbolic with respect to a real linear space $V$ of dimension $\ell1$
if $X \cap V = \emptyset$ and $X$ intersects any real linear space of dimension $\ell$ through $V$
in real points only.
Alternatively, if $Y$ is the associated hypersurface of $X$ in the Grassmanian ${\mathbb G}(\ell1,d)$
of $\ell1$dimensional linear spaces in ${! \mathbb P}^d$, then $V \not\in Y$ and $Y$ intersects any
real onedimensional Schubert cycle through $V$ in real points only.
In the case $\ell=1$, i.e., $X$ is a hypersurface, this simply means that $X$ is the zero locus of a homogeneous
hyperbolic polynomial.
I will discuss hyperbolic subvarieties of a higher codimension, the analogues of hyperbolicity cones,
and a class of definite Hermitian determinantal representations that witnesses hyperbolicity.
It turns out that the analogue of the Lax conjecture holds  any real curve in ${\mathbb P}^d$ that is hyperbolic
with respect to some $d2$dimensional linear space admits a definite Hermitian, or even real symmetric, determinantal representation.
 Supplements


