Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
From MaRDI portal
Cites work
- (2+)-Sat is NP-hard
- A Random Recolouring Method for Graphs and Hypergraphs
- Approximate hypergraph coloring under low-discrepancy and related promises
- Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width at least four
- Conditional Hardness for Approximate Coloring
- Existence theorems for weakly symmetric operations
- Gaussian bounds for noise correlation of functions
- Hardness of Approximate Hypergraph Coloring
- Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs
- Hardness of rainbow coloring hypergraphs
- scientific article; zbMATH DE number 3829252 (Why is no real title available?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improved Inapproximability of Rainbow Coloring
- Inapproximability of hypergraph vertex cover and applications to scheduling problems
- Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
- New hardness results for graph and hypergraph colorings
- Noise stability of functions with low influences: invariance and optimality
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- Rainbow coloring hardness via low sensitivity polymorphisms
- Sensitivity versus certificate complexity of Boolean functions
- Some optimal inapproximability results
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- The hardness of 3-uniform hypergraph coloring
- The quest for strong inapproximability results with perfect completeness
- Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
Cited in
(2)
This page was built for publication: Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875467)
