Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
From MaRDI portal
Publication:5217824
DOI10.1137/19M127731XzbMath1448.68356OpenAlexW3007912722MaRDI QIDQ5217824
Sai Sandeep, Venkatesan Guruswami
Publication date: 26 February 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m127731x
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Topology and Adjunction in Promise Constraint Satisfaction, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Noise stability of functions with low influences: invariance and optimality
- Galois theory for minors of finite functions
- 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
- CREW PRAM<scp>s</scp> and Decision Trees
- 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
- Algebraic approach to promise constraint satisfaction
- Classifying the Complexity of Constraints Using Finite Algebras
- 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
