On the NP-hardness of MAX-Not-2

DOI10.1137/120882718zbMATH Open1359.68105OpenAlexW1979065044WikidataQ56958755 ScholiaQ56958755MaRDI QIDQ5419035FDOQ5419035

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

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

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)

Cited In (10)

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

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)