Universal factor graphs for every NP-hard Boolean CSP

DOI10.4230/LIPICS.APPROX-RANDOM.2014.274MaRDI QIDQ2969623zbMATH OpenOpenAlexFDO

Authors Shlomo Jozeph

Publication date 22 March 2017

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2014/4702/pdf/19.pdf/

zbMATH Keywords

hardness of approximationhardness with preprocessing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Universal factor graphs
• Hard constraint satisfaction problems have hard gaps at location 1
• scientific article; zbMATH DE number 1559517
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
• The Nonapproximability of Non-Boolean Predicates

Cited in

(3)

• Universal factor graphs
• Max-3-Lin over non-abelian groups with universal factor graphs
• Optimal inapproximability with universal factor graphs

This page was built for publication: Universal factor graphs for every NP-hard Boolean CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2969623)