Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SAI SANDEEP:
All reports by Author Sai Sandeep:

TR19-116 | 9th September 2019
Venkatesan Guruswami, Sai Sandeep

$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ ... more >>>




ISSN 1433-8092 | Imprint