Abstract
In this talk we discuss two main results:
(1) We prove that for any delta > 0 and any symmetric convex body with Gaussian measure at least exp(-delta*n) one can find a partial coloring in a constant scaling of K in polynomial time. That partial coloring is guaranteed to have a linear number of coordinates in {-1,1}.
(2) A seminal result by Batson, Spielman and Srivastava from 2008 shows that any undirected graph admits a linear size spectral sparsifier. One can define a convex body of all good fractional signings. We can indeed prove that this body is close to most of the Gaussian measure.
This implies that the algorithm from above can be used to sample a linear size sparsifer. In contrast to previous methods, we require only a logarithmic number of sampling phases. A byproduct of the proof is the inside that the discussed body of good signing has a high mean width.
This is joint work with Victor Reis.