[A&C Seminar] Beating the Union Bound via Geometric Techniques
Speaker: Raghu Meka, IAS
Date: Wednesday, February 6 2013
Time: 4:00PM to 5:00PM
Location: 32-G575
Contact: Eric Price, ecprice@mit.edu
Relevant URL: http://www.mit.edu/~ecprice/algcompsem/
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) Optimal size, explicit eps-nets for computing Gaussian integrals.
Besides being interesting on its own, our result has applications to
computing the supremum of Gaussian processes and cover times of graphs.
2) A new elementary and constructive proof of Spencer's celebrated six
standard deviations suffice theorem. We introduce a new 'entropic'
rounding technique that can be used in a variety of algorithmic settings and
appears to have much broader potential.
For both problems, our methods critically exploit certain geometric and
symmetry properties of the Gaussian space.
See other events happening in February 2013
