Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

Stochastic local search and the Lovasz Local Lemma

Fotis Iliopoulos (IAS)

Location:  Core 301
Date & time: Wednesday, 04 March 2020 at 11:00AM - 12:00PM

Abstract: Numerous problems in computer science and combinatorics can be formulated as searching for objects lacking certain bad properties, or "flaws". For example, constraint satisfaction problems like satisfiability can be seen as searching for objects (truth assignments) that are flawless in the sense that they do not violate any constraint. A large class of practical algorithms for finding flawless objects employ "stochastic local search"; such algorithms start with a flawed object and try to make it flawless via small randomized changes that in each step focus on eradicating a specific flaw (while potentially introducing others).

In this talk, I will present a general framework for the design and analysis of stochastic local search algorithms, inspired by and extending the Lovasz Local Lemma. I will also talk about its applications in solving "pseudo-random" instances of constraint satisfaction problems.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.