Beating the Union Bound via Geometric Techniques

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.

Speaker Details

Raghu Meka is currently a postdoctoral fellow at the Institute for Advanced Study, Princeton and DIMACS, Rutgers. He received his PhD from the department of computer science at the University of Texas at Austin in 2011. He is a recipient of the Bert Kay best dissertation award, the Dean’s Excellence award and an MCD fellowship at UT Austin. Prior to joining UT Austin, he completed his B.Tech in computer science from Indian Institute of Technology, Chennai, India. His main interests are in complexity theory, pseudo-randomness, algorithm design, learning theory and data mining.

Date:
Speakers:
Raghu Meka
Affiliation:
Institute for Advanced Study, Princeton

    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Raghu Meka

      Raghu Meka