Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
From MaRDI portal
Publication:5875467
DOI10.4230/LIPIcs.APPROX-RANDOM.2019.15OpenAlexW2978153430MaRDI QIDQ5875467
Sai Sandeep, Venkatesan Guruswami
Publication date: 3 February 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11230/pdf/LIPIcs-APPROX-RANDOM-2019-15.pdf/
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Noise stability of functions with low influences: invariance and optimality
- Existence theorems for weakly symmetric operations
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- The hardness of 3-uniform hypergraph coloring
- Gaussian bounds for noise correlation of functions
- Hardness of Approximate Hypergraph Coloring
- Conditional Hardness for Approximate Coloring
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
- Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
- A Random Recolouring Method for Graphs and Hypergraphs
- The Quest for Strong Inapproximability Results with Perfect Completeness
- Hardness of Rainbow Coloring Hypergraphs
- Improved hardness for H-colourings of G-colourable graphs
- Improved Inapproximability of Rainbow Coloring
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
- $(2+\varepsilon)$-Sat Is NP-hard
- New hardness results for graph and hypergraph colorings
- Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
- Some optimal inapproximability results
- Sensitivity Versus Certificate Complexity of Boolean Functions
