Conditional hardness for satisfiable 3-CSPs

DOI10.1145/1536414.1536482MaRDI QIDQ5172744zbMATH OpenOpenAlexFDO

Authors Ryan O'Donnell, Yi Wu

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536482

zbMATH Keywords

hardness of approximationKhot's conjecturePCPsatisfiable \(3\)-CSPs

Mathematics Subject Classification ID

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

Recommendations

• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• Computational complexity of some restricted instances of 3-SAT
• Computationally hard problems: 3-SAT and its polynomial solvability
• Hard random 3-SAT problems and the Davis-Putnam procedure
• Hard satisfiable 3-SAT instances via autocorrelation
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
• An efficient algorithm for the 3-satisfiability problem
• scientific article; zbMATH DE number 437557
• On the limit of branching rules for hard random unsatisfiable 3-SAT

Cited in

(16)

• Approximating satisfiable satisfiability problems
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• Stronger methods of making quantum interactive proofs perfectly complete
• On the NP-hardness of Max-Not-2
• Conditional Hardness of Approximating Satisfiable Max 3CSP-q
• 3-bit dictator testing: 1 vs. 5/8
• Query-efficient dictatorship testing with perfect completeness
• The quest for strong inapproximability results with perfect completeness
• Hard satisfiable 3-SAT instances via autocorrelation
• An improved dictatorship test with perfect completeness
• On the NP-hardness of MAX-Not-2
• scientific article; zbMATH DE number 7716602 (Why is no real title available?)
• d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
• On approximability of satisfiable k-CSPs: V
• Approximating satisfiable satisfiability problems (extended abstract)

This page was built for publication: Conditional hardness for satisfiable 3-CSPs

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