CSP and MMSNP are computationally equivalent
Seminar Room 1, Newton Institute
We introduce the notion of expander hypergraphs as one natural generalisation of expander graphs. We give an efficient construction of expander hypergraphs. This new tool makes possible to derandomise Feder and Vardi's reduction of CSP to large girth CSP. This implies the derandomisation of the computational equivalence between the classes CSP and MMSNP (Monotone monadic SNP).
Theorem: For every language L in MMSNP there are relational structures S1, ... ,Sn such that the following hold.
(1) L has a polynomial reduction to the union of the languages CSP(Si). (2) For every i the language CSP(Si) has a polynomial reduction to L.