The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

LAA

Seminar

CSP and MMSNP are computationally equivalent

Kun, G (Eotvos)
Monday 13 March 2006, 11:00-12:00

Seminar Room 1, Newton Institute

Abstract

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.

Back to top ∧