IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

The Algorithmic Local Lemma

  • April 24, 2012
  • 3 p.m.
  • LeConte 412


The Lov\'asz Local Lemma says that in a probability space, a collection of events with non-zero probability and limited dependencies will behave like independent events, in the sense that the probability of their intersection will be non-zero. While purely an existential statement, Moser and Tardos provide an algorithmic proof of the Local Lemma with fast expected runtime which provides a point in the probability space which witnesses the intersection of the events in question occurring. We will provide an overview of the Local Lemma with proof, followed by an analysis of the random algorithm provided by Moser and Tardos. We then look at the Local Lemma algorithm applied to the Pythagorean triples hypergraph.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster