$(2+\varepsilon)$-Sat Is NP-hard

DOI10.1137/15M1006507zbMath1476.68188OpenAlexW2758570758MaRDI QIDQ5363382

Per Austrin, Johan T. Håstad, Venkatesan Guruswami

Publication date: 6 October 2017

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

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

zbMATH Keywords

discrepancyconstraint satisfactionprobabilistically checkable proofscomplexity dichotomypolymorphismshypergraph coloring

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (17)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Small Promise CSPs that reduce to large CSPs ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Unnamed Item ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ Minimizing worst-case and average-case makespan over scenarios ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ On the Computational Complexity of Linear Discrepancy ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ Revisiting alphabet reduction in Dinur’s PCP. ⋮ The Geometry of Differential Privacy: The Small Database and Approximate Cases ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮ Hardness of Rainbow Coloring Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation resistant predicates from pairwise independence
• Gaussian bounds for noise correlation of functions
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Scheduling over Scenarios on Two Machines
• On the usefulness of predicates
• Proof verification and the hardness of approximation problems
• A threshold of ln n for approximating set cover
• On the power of unique 2-prover 1-round games
• A Parallel Repetition Theorem
• Classifying the Complexity of Constraints Using Finite Algebras
• Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs
• $(2+\varepsilon)$-Sat Is NP-hard
• New hardness results for graph and hypergraph colorings
• The complexity of satisfiability problems
• Some optimal inapproximability results
• Approximating Linear Threshold Predicates
• Rigorous results for random (\(2+p)\)-SAT

This page was built for publication: $(2+\varepsilon)$-Sat Is NP-hard