Title: Derandomizing Feder-Vardi
Speaker: Gabor Kun, IAS
Date: Wednesday, November 19, 2008 11:00-12:00pm
Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In their seminal paper Feder and Vardi proved that every problem in the class Monotone Monadic Strict NP (MMSNP) is random polynomial-time equivalent to a finite union of Constraint Satisfaction Problems (CSP). The class MMSNP is the "largest natural" subclass defined by syntactical restrictions on existential, second order formulas that might have the dichotomy property. This was the main reason for the famous dichotomy conjecture of Feder and Vardi for CSP problems.
We derandomize their reduction showing that every MMSNP problem is polynomial-time equivalent to a finite union of CSP problems. The technical novelty of the paper is a notion of expander relational structures. We give a polynomial-time construction of such structures with large girth. We show another interesting application of these structures: we give an effective construction of hypergraphs with large girth and chromatic number.