Beating the Union Bound via Geometric Techniques

Опубликовано 8 августа 2016, 17:59

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: 1) A new elementary and constructive proof of Spencer's celebrated six standard deviations suffice theorem. We introduce a new LP rounding technique that can potentially be used in a variety of algorithmic settings and appears to have much broader potential. 2) A central limit theorem for polytopes with an error bound that is only poly-logarithmic in the number of bounding faces of the polytope. Besides being interesting on its own, the limit theorem has applications to problems in pseudo-randomness and learning theory. For both problems, our methods critically exploit certain geometric and symmetry properties of the Gaussian space.