On the NP-hardness of MAX-Not-2

DOI10.1137/120882718MaRDI QIDQ5419035zbMATH OpenOpenAlexWikidataFDO

Authors Johan Hastad

Publication date 4 June 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/120882718

zbMATH Keywords

approximation resistanceconstraint satisfactionprobabilistically checkable proofs

Mathematics Subject Classification ID

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

Recommendations

• On the NP-hardness of Max-Not-2
• Conditional hardness for satisfiable 3-CSPs
• Is constraint satisfaction over two variables always easy?
• scientific article; zbMATH DE number 2019637
• On the NP-hardness of approximating ordering-constraint satisfaction problems

Cited in

(12)

• More complicated questions about maxima and minima, and some closures of NP
• On the robust hardness of Gröbner basis computation
• Max NP-completeness made easy
• On the NP-hardness of Max-Not-2
• The quest for strong inapproximability results with perfect completeness
• An improved dictatorship test with perfect completeness
• Robust algorithms with polynomial loss for near-unanimity CSPs
• A toolbox for barriers on interactive oracle proofs
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• Optimal inapproximability with universal factor graphs
• On approximability of satisfiable k-CSPs: V
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring

This page was built for publication: On the NP-hardness of MAX-Not-2

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