Speaker Raghu Meka
Affiliation Institute for Advanced Study, Princeton
Host Yuval Peres
Date recorded 21 February 2013
The union bound is one of the mainstays of the probabilistic method and analysis of randomized algorithms. However, this simplistic approach does not give the full picture for many important cases, with Lovasz local lemma being a particularly salient example. In this talk I will discuss two recent results that go beyond the union bound via geometric techniques:
For both problems, our methods critically exploit certain geometric and symmetry properties of the Gaussian space.
©2013 Microsoft Corporation. All rights reserved.