REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR13-122 | 10th May 2014 15:10

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

Revision #1
Authors: Irit Dinur, Venkatesan Guruswami
Accepted on: 10th May 2014 15:10
Keywords:

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 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$.

Changes to previous version:

Several editorial changes as part of journal revision; the long code based hypergraph coloring result (in Appendix B) is weakened from 6-uniform hypergraphs to 8-uniform hypergraphs.

### Paper:

TR13-122 | 5th September 2013 17:16

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

TR13-122
Authors: Irit Dinur, Venkatesan Guruswami
Publication: 5th September 2013 17:17
Keywords:

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 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$.

ISSN 1433-8092 | Imprint
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7834625244140625, "perplexity": 1195.8541710553209}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-44/segments/1476988719754.86/warc/CC-MAIN-20161020183839-00262-ip-10-171-6-4.ec2.internal.warc.gz"}