A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
From MaRDI portal
Publication:5317188
DOI10.1137/S0097539704443057zbMath1079.68039MaRDI QIDQ5317188
Irit Dinur, Subhash A. Khot, Venkatesan Guruswami, Oded Regev
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
hardness of approximation; probabilistically checkable proof; hypergraph vertex cover; long-code; multilayered outer verifier
05C65: Hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Approximating Partially Bounded Degree Deletion on Directed Graphs, Inapproximability of $H$-Transversal/Packing, The Minimum Substring Cover Problem, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Complexity of approximating CSP with balance/hard constraints, Approximation and hardness results for the maximum edge \(q\)-coloring problem, Partial multicovering and the \(d\)-consecutive ones property, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Hardness of approximating the closest vector problem with pre-processing, Approximating vertex cover in dense hypergraphs, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Register loading via linear programming, Optimization problems in multiple subtree graphs, Minimizing the sum of weighted completion times in a concurrent open shop, Approximability of sparse integer programs, Approximating integer programs with positive right-hand sides, The ordered covering problem, The minimum substring cover problem, Noise stability of functions with low influences: invariance and optimality, Cooperative TSP, Towards a characterization of constant-factor approximable finite-valued CSPs, Tight approximation bounds for dominating set on graphs of bounded arboricity, The \(k\)-hop connected dominating set problem: approximation and hardness, Complexity and lowers bounds for power edge set problem, Metrical service systems with multiple servers, Restricted parameter range promise set cover problems are easy, Paging with request sets, Set cover problems with small neighborhood covers, Efficiency and complexity of price competition among single-product vendors, Primal-dual algorithms for precedence constrained covering problems, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Primal-Dual Algorithms for Precedence Constrained Covering Problems
