ECCC-Report TR13-122https://eccc.weizmann.ac.il/report/2013/122Comments and Revisions published for TR13-122en-usSat, 10 May 2014 15:10:07 +0300
Revision 1
| PCPs via the low-degree long code and hardness for constrained hypergraph coloring |
Irit Dinur,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2013/122#revision1We 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^{\Omega(\sqrt{\log \log N})})$ number of colors where $N$ is the number of vertices. This is the first hardness result to go beyond the $O(\log N)$ barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known $O(\log \log N)$-coloring hardness for $2$-colorable hypergraphs, and an exponential improvement over the $(\log N)^{\Omega(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^{\Omega(\sqrt{\log \log N})}$ 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 $(\log N)^{\Omega(1)}$-coloring $2$-colorable $8$-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 $\beta : {\mathbb F}_2^m \to {\mathbb F}_2$ is $2^{\Omega(d)}$ far in absolute distance from polynomials of degree $m-d$, then the probability that $\deg(\beta g) \le m-3d/4$ for a random degree $d/4$ polynomial $g$ is {\em doubly exponentially} small in $d$.
Sat, 10 May 2014 15:10:07 +0300https://eccc.weizmann.ac.il/report/2013/122#revision1
Paper TR13-122
| PCPs via low-degree long code and hardness for constrained hypergraph coloring |
Irit Dinur,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2013/122We 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^{\Omega(\sqrt{\log \log N})})$ number of colors where $N$ is the number of vertices. This is the first hardness result to go beyond the $O(\log N)$ barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known $O(\log \log N)$-coloring hardness for $2$-colorable hypergraphs, and an exponential improvement over the $(\log N)^{\Omega(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^{\Omega(\sqrt{\log \log N})}$ 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 $(\log N)^{\Omega(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 $\beta : {\mathbb F}_2^m \to {\mathbb F}_2$ is $2^{\Omega(d)}$ far in absolute distance from polynomials of degree $m-d$, then the probability that $\deg(\beta g) \le m-3d/4$ for a random degree $d/4$ polynomial $g$ is {\em doubly exponentially} small in $d$.
Thu, 05 Sep 2013 17:17:51 +0300https://eccc.weizmann.ac.il/report/2013/122