Conditional hardness for satisfiable 3-CSPs

DOI10.1145/1536414.1536482zbMath1304.68080OpenAlexW2008724760MaRDI QIDQ5172744

Yi Wu, Ryan O'Donnell

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 approximationPCPKhot's conjecturesatisfiable \(3\)-CSPs

Mathematics Subject Classification ID

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

Related Items (5)

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ Unnamed Item ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ An Improved Dictatorship Test with Perfect Completeness

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