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

constraint satisfactionprobabilistically checkable proofsapproximation resistance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

(10)

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

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)