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.In particular, we show a hardness for a variant of hypergraph coloring (with hyperedges of size 6), with a gap between 2 and exp(2(loglogN)) number of colors where N is the number of vertices. This is the first hardness result to go beyond the O(logN) barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known O(loglogN)-coloring hardness for 2-colorable hypergraphs, and an exponential improvement over the (logN)(1)-coloring hardness for O(1)-colorable hypergraphs. Stated in terms of ``covering complexity," we show that for 6-ary Boolean CSPs, it is hard to decide if a given instance is perfectly satisfiable or if it requires more than 2(loglogN) assignments for covering all of the constraints.While our methods do not yield a result for conventional hypergraph coloring due to some technical reasons, we also prove hardness of (logN)(1)-coloring 2-colorable 6-uniform hypergraphs (this result relies just on the long code).A key algebraic result driving our analysis concerns a very low-soundness error testing method for Reed-Muller codes. We prove that if a function :F2mF2 is 2(d) far in absolute distance from polynomials of degree m?d, then the probability that deg(g)m?3d4 for a random degree d4 polynomial g is {em doubly exponentially} small in d.
展开▼
