Title: Derandomizing Feder-Vardi

Speaker: Gabor Kun, IAS 

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.