A new multilayered PCP and the hardness of hypergraph vertex cover
From MaRDI portal
Publication:3581279
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
Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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