PCPs via the low-degree long code and hardness for constrained hypergraph coloring

DOI10.1007/s11856-015-1231-3zbMath1330.68091OpenAlexW2256256972MaRDI QIDQ891178

Irit Dinur, Venkatesan Guruswami

Publication date: 16 November 2015

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11856-015-1231-3

Mathematics Subject Classification ID

Hypergraphs (05C65) Linear codes (general theory) (94B05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, A Characterization of hard-to-cover CSPs, Hardness of Rainbow Coloring Hypergraphs

Cites Work

• Unnamed Item
• PCP characterizations of NP: toward a polynomially-small error-probability
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• The complexity of equality constraint languages
• Noise stability of functions with low influences: invariance and optimality
• The hardness of 3-uniform hypergraph coloring
• Efficient probabilistic checkable proofs and applications to approximation
• Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
• Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
• Hardness of Approximate Hypergraph Coloring
• The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
• Making the Long Code Shorter
• Hardness results for approximate hypergraph coloring
• On the power of unique 2-prover 1-round games
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Optimal Testing of Reed-Muller Codes
• Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
• On the NP-Hardness of Max-Not-2
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A PRG for lipschitz functions of polynomials with applications to sparsest cut