Abstract | ||
---|---|---|
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 hyper graph coloring (with hyper edges of size 6), with a gap between 2 and exp(2Ω(□log log N)) number of colors where N is the number of vertices. This is the first hardness result to go beyond the Õ(log N) barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known Õ(log log N)-coloring hardness for 2-colorable hyper graphs, and an exponential improvement over the (log N)Ω(1)-coloring hardness for Õ(1)-colorable hyper graphs. 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Ω(□log log N) assignments for covering all of the constraints. While our methods do not yield a result for conventional hyper graph coloring due to some technical reasons, we also prove hardness of (log N)Ω(1)-coloring 2-colorable 6-uniform hyper graphs (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 β : F_2m to F_2 is 2Ω(d) far in absolute distance from polynomials of degree m-d, then the probability that °(β g) ≤ m-3d/4 for a random degree d/4 polynomial g is doubly exponentially small in d. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/FOCS.2013.44 | Foundations of Computer Science |
Keywords | DocType | Volume |
conventional hyper graph,log log n,colorable hyper graph,2-colorable 6-uniform hyper graph,long code,low-degree long code,hardness result,coloring hardness,hyper edge,constrained hypergraph coloring,2-colorable hyper graph,exponential improvement,reed muller codes,fourier analysis,polynomials,boolean algebra,probability,computational complexity,constraint satisfaction problems | Journal | 20 |
Issue | ISSN | Citations |
2 | 1565-8511 | 9 |
PageRank | References | Authors |
0.72 | 12 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Irit Dinur | 1 | 1187 | 85.67 |
V. Guruswami | 2 | 3205 | 247.96 |