A Recent NP-Hardness Result for Approximation of 3-Coloring

The speaker will present a recent result by Austrin et al. on the NP-hardness of 3-coloring a 3-colorable graph with at least $\frac{16}{17} + \epsilon$ of the edges bichromatic. Austrin et al.'s result is notable for its use of Fourier analysis over $\mathbb{Z}_3$. He will also review the general approach for developing NP-hardness of approximation results through probabilistically checkable proofs (PCPs) for the label cover proble