PCPs via the low-degree long code and hardness for constrained hypergraph coloring

摘要

We develop new techniques to incorporate the recently proposed "short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical "label-cover + Fourier Analysis" framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs and certain coloring-type problems.