Can I read Constraints, MMSNP and expander relational structures on EtoBox?

Constraints, MMSNP and expander relational structures by Kun, Gabor is a scholarly article available to read on EtoBox.

What is Constraints, MMSNP and expander relational structures about?

We give a poly-time construction for a combinatorial classic known as Sparse Incomparability Lemma, studied by Erdos, Lovasz, Nesetril, Rodl and others: We show that every Constraint Satisfaction Problem is poly-time equivalent to its restriction to structures with large girth. This implies that the complexity classes CSP and Monotone Monadic Strict NP introduced by Feder and Vardi are computationally equivalent. The technical novelty of the paper is a concept of expander relations and a new type of product for relational structures: a generalization of the zig-zag product, the twisted product.

Author

Kun, Gabor

Published

2007

Language

EN