Constraints, Logic and Derandomization

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Constraints, Logic and Derandomization
Speaker:Gabor Kun
Affiliation:Simon Fraser University and Member, School of Mathematics
Date:Tuesday, May 26
Time/Room:10:30am - 12:30pm/S-101

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.