A Characterization of hard-to-cover CSPs
From MaRDI portal
Publication:5857608
DOI10.4086/toc.2020.v016a016zbMath1477.68114OpenAlexW3115015447MaRDI QIDQ5857608
Amey Bhangale, Prahladh Harsha, Girish Varma
Publication date: 1 April 2021
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2020.v016a016
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- Zero knowledge and the chromatic number
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Gaussian bounds for noise correlation of functions
- Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs
- 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
- Proof verification and the hardness of approximation problems
- Making the Long Code Shorter
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Some optimal inapproximability results
