On the NP-Hardness of Max-Not-2
From MaRDI portal
Publication:5419035
DOI10.1137/120882718zbMath1359.68105OpenAlexW1979065044WikidataQ56958755 ScholiaQ56958755MaRDI QIDQ5419035
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (7)
PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ A toolbox for barriers on interactive oracle proofs ⋮ On the robust hardness of Gröbner basis computation ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ An Improved Dictatorship Test with Perfect Completeness
This page was built for publication: On the NP-Hardness of Max-Not-2
