Improved Inapproximability of Rainbow Coloring

DOI10.1137/1.9781611975994.90OpenAlexW3003147155MaRDI QIDQ5146867

Amey Bhangale, Aditya Potukuchi, Per Austrin

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1810.02784

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (5)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

This page was built for publication: Improved Inapproximability of Rainbow Coloring