Three‐query PCPs with perfect completeness over non‐Boolean domains

DOI10.1002/rsa.20050zbMath1161.68848OpenAlexW1549730417MaRDI QIDQ5311912

Jonas Holmerin, Lars Engebretsen

Publication date: 29 August 2005

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20050

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (1)

More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

Cites Work

• Hardness results for approximate hypergraph coloring
• Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε

This page was built for publication: Three‐query PCPs with perfect completeness over non‐Boolean domains