A new multilayered PCP and the hardness of hypergraph vertex cover

DOI10.1145/780542.780629zbMath1192.68290OpenAlexW2004012902MaRDI QIDQ3581279

Subhash A. Khot, Irit Dinur, Venkatesan Guruswami, Oded Regev

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (13)

Is constraint satisfaction over two variables always easy? ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ Path coupling using stopping times and counting independent sets and colorings in hypergraphs ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ Approximation of the quadratic set covering problem ⋮ On the Minimum Hitting Set of Bundles Problem ⋮ Approximating Single Machine Scheduling with Scenarios ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ Disjoint bases in a polymatroid ⋮ More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ On the minimum hitting set of bundles problem

This page was built for publication: A new multilayered PCP and the hardness of hypergraph vertex cover