## Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions

Girish Varma ∗

December 13, 2014

## Abstract

In a recent result, Khot and Saket [FOCS 2014] proved the quasi-NP-hardness of coloring a 2 -colorable 12 -uniform hypergraph with 2 (log n ) Ω(1) colors. This result was proved using a novel outer PCP verifier which had a strong soundness guarantee. We reduce the arity in their result by modifying their 12-query inner verifier to an 8-query inner verifier based on the hypergraph coloring hardness reductions of Guruswami et. al. [STOC 2014]. More precisely, we prove quasi-NP-hardness of the following problems on n -vertex hypergraphs.

- · Coloring a 2 -colorable 8 -uniform hypergraph with 2 (log n ) Ω(1) colors.
- · Coloring a 4 -colorable 4 -uniform hypergraph with 2 (log n ) Ω(1) colors.

## 1 Introduction

The discovery of the low-degree long code aka short code by Barak et. al. [BGH + 12] has over the last one year led to a sequence of results improving our understanding of the hardness of constant colorable hypergraphs with as few colors as possible. A k -uniform hypergraph is a collection of vertices and hyperedges such that every hyperedge is a subset of k vertices. A hypergraph is said to be q -colorable if the vertices of the hypergraph can be colored with at most q colors such that no hyperedge is monochromatic. An independent set in a hypergraph is a collections of vertices such that no hyperedge is wholly contained within the collection. Note that a hypergraph is q -colorable iff it the set of vertices can be partitioned into at most q independent sets.

Prior to the low-degree long code, all hardness reductions for hypergraph coloring where proved using the long code [BGS98] which resulted in a huge disparity between the best known positive and negative results for hypergraph coloring: the best known approximation algorithms require at least n Ω(1) colors to color a constant colorable (hyper)graph while the inapproximability results could only rule out at best (log n ) O (1) colors. The situation was redeemed by introduction of the low-degree long code, a derandomization of the long code, which was then adapted by Dinur and Guruswami [DG14] toward proving inapproximability results. Building on the DinurGuruswami framework, Guruswami et. al. [GHH 14] showed that it is quasi-NP-hard to color a + 2-colorable 8-uniform hypergraph with 2 2 Ω( √ log log n ) colors. Both the Dinur-Guruswami and Guruswami et. al. results were obtained by modifying the innermost PCP verifier to work with the

∗ Tata Institute of Fundamental Research, India. Supported by Google India under the Google India PhD Fellowship Award. Email : girishrv@tifr.res.in

low-degree long code. Shortly thereafter, in a remarkable improvement, Khot and Saket [KS14] showed that it is quasi-NP-hard to color a 2-colorable 12-uniform hypergraph with 2 (log n ) Ω(1) colors. They obtained this result by using an 12-query inner PCP verifier based on the quadratic code, ie., a low-degree long code with degree two. However, to use a quadratic code based inner verifier, they needed an outer PCP verifier with a significantly stronger soundness guarantee than the standard outer PCP verifier obtained from parallel repetition of the PCP Theorem. In particular, they needed an outer PCP verifier, which in the soundness case, would not be satisfied by a short list of proofs even in superposition 1 . The construction of this outer PCP verifier with this stronger soundness guarantee is the main technical ingredient in the result of Khot and Saket [KS14]. We show that this outer PCP verifier of Khot and Saket can in fact be combined with a 8-query inner PCP verifier based on the Guruswami et. al. inner PCP verifier to obtain a hardness result for 2-colorable 8-uniform hypergraphs. More precisely, we show the following.

Theorem 1.1. For every constant /epsilon1 &gt; 0 there is a quasi-polynomial time reduction from 3 -SAT to a 8 -uniform hypergraph G on n vertices such that,

- 1. YES Case: If the 3 -SAT instance is satisfiable then G is 2 -colorable.
- 2. NO Case: If the 3 -SAT instance is unsatisfiable then G does not have an independent set of relative size 2 -(log n ) 1 20 -/epsilon1 .

Guruswami et. al. [GHH 14] also proved how to reduce the uniformity in certain reductions + from 8 to 4 at the cost of increasing the number of colors from 2 to 4. We note that a similar trick can be performed in our setting to obtain the following result.

Theorem 1.2. For every constant /epsilon1 &gt; 0 there is a quasi-polynomial time reduction from 3 -SAT to a 4 -uniform hypergraph G on n vertices such that,

- 1. YES Case: If the 3 -SAT instance is satisfiable then G is 4 -colorable.
- 2. NO Case: If the 3 -SAT instance is unsatisfiable then G does not have an independent set of relative size 2 -(log n ) 1 20 -/epsilon1 .

We remark that the analyses of the inner verifier in both the above theorems is simpler than the analyses of the corresponding inner verifiers in Guruswami et. al. and Khot-Saket results. Furthermore, in the language of covering complexity 2 introduced by Guruswami, H˚ astad and Sudan [GHS00], (the proof of) Theorem 1.2 demonstrates a Boolean 4CSP for which it is quasi-NPhard to distinguish between covering number of 2 vs. (log n ) Ω(1) .

## 2 Preliminaries

Let F denote the field GF (2) . Let F m m × be the vector space of m × m matrices over the field F . Our inner verifier is based on the quadratic code, which is a specialization of the low degree long code to degree 2 .

1 We will not require the exact definition of satisfying in superposition for this note. See Theorem 2.2 for the details of the Khot-Saket outer PCP verifier.

2 The covering number of a CSP is the minimal number of assignments to the vertices so that each hyperedge is covered by at least one assignment.

Definition 2.1 (Quadratic Code) . The quadratic code of x ∈ F m is a function A x : F m m × → F defined as A x ( X ) := 〈 X,x ⊗ x 〉 .

Our reductions makes use of the following outer PCP verifier of Khot and Saket [KS14]. As stated in the introduction, these instances have stronger soundness conditions which make them amenable for composition with a quadratic code based inner verifier.

Theorem 2.2 ([KS14, Theorem 7.2]) . There is a quasi-polynomial time reduction from an instance of 3 -SAT to a bi-regular instance ( U, V, E, Π) of Label Cover such that

- · Vertex sets U and V are bounded in size by N .
- · The label sets are F r × r 2 , F m m × 2 for U and V respectively.
- · For e ∈ E , the map π e : F m m × 2 → F r × r 2 is a linear transformation that maps symmetric matrices to symmetric matrices . 3 For an r × r matrix X X , ◦ π e is the unique m × m matrix such that 〈 X ◦ π , Y e 〉 = 〈 X,π Y e 〉 .
- · For each vertex v ∈ V , there is a constraint C v that is a a conjunction of homogeneous linear equations on the entries of the m × m matrix label.
- · δ ≤ 2 -log 1 / 3 N and k ≥ (log N ) 1 9 / .

The reduction satisfies:

- 1. Completeness : If the 3 -SAT instance is satisfiable then there is a labeling x u ⊗ x u for u ∈ U and y v ⊗ y v for v ∈ V such that
- · for each v ∈ V , y v ∈ F m 2 has the m th coordinate 1 and y v ⊗ y v satisfies the constraint C v ,
- · for each ( u, v ) ∈ E π , u,v ( y v ⊗ y v ) = x u ⊗ x u .
- 2. Soundness : If the 3 -SAT instance is not satisfiable then the following cannot hold: There are symmetric matrices M u ∈ F r × r 2 , M v ∈ F m m × 2 for u ∈ U, v ∈ V of rank ≤ k such that
- · for each v ∈ V , M v ∈ F m m × 2 has the ( m,m ) th coordinate 1 and M v satisfies the constraint C v ,
- · for δ fraction of edges e , π e ( M v ) = M u .
- 3. Smoothness : For any v ∈ V and any symmetric non-zero matrix M v with rank ≤ k , over a random choice of an edge e incident on v ,

$$\Pr [ \pi _ { e } ( M _ { v } ) = 0 ] \leq \delta / 2.$$

## 3 2 -colorable 8 -uniform hypergraphs

In this section we prove Theorem 1.1. Our reduction starts from the label cover instances given by Theorem 2.2. Let ( U, V, E, Π) be an instance of the label cover. We will construct a hypergraph G = ( V E , ) . For v ∈ V , let H v ⊆ F m m × 2 be the dual of the subspace of the set matrices that are symmetric and which satisfies the constraint C v . The set of vertices V will be the same as

3 The property that π maps symmetric matrices to symmetric matrices is easy to see from the proof of [KS14, Theorem 7.2].

V × ( F m m × 2 / H v ) . Any 2 -coloring of G is a collection of functions A ′ v : F m m × 2 / H v → { 0 1 , } for v ∈ V . For any such function, we can uniquely extend it to get A v : F m m × 2 → { 0 1 , } which is constant over cosets of H v . This method is called folding and it ensures that A v satisfies the following: if α ∈ F m m × 2 is such that ̂ A v ( α ) is non-zero, then α is symmetric and satisfies C v .

The set of edges E will be defined by the test mentioned below, which checks whether a supposed 2 -coloring A ′ v : F m m × 2 / H →{ v 0 1 , } is valid. There is an edge in E between any set of vertices in V that are queried together by the test. The test will be querying the extended functions A v at matrices in F m m × 2 instead of A ′ v . So a query to A v at X ∈ F m m × 2 corresponds to a query to A ′ v at the coset of H v that contains X .

## 2 -Colorable 8 -Uniform Test T 2 8 ,

- 1. Choose u ∈ U uniformly at random and v, w ∈ V uniformly and independently at random from the neighbors of u . Let π, σ : F m m × 2 → F r × r 2 be the projections corresponding to the edges ( u, v ) , ( u, w ) respectively. Uniformly and independently at random choose X ,X ,Y ,Y 1 2 1 2 ∈ F m m × 2 and x, y, z, x , y , z ′ ′ ′ ∈ F m 2 and F ∈ F r × r 2 . Let e m ∈ F m 2 be the vector with only the m th entry 1 and the rest is 0 .
- 2. Accept if and only if the following 8 values are not all equal :

A v ( X 1 ) A v ( X 3 ) where X 3 := X 1 + x ⊗ y + F ◦ π A v ( X 2 ) A v ( X 4 ) where X 4 := X 2 +( x + e m ) ⊗ z + F ◦ π A w ( Y 1 ) A w ( Y 3 ) where Y 3 := Y 1 + x ′ ⊗ y ′ + F ◦ σ + e m ⊗ e m A w ( Y 2 ) A w ( Y 4 ) where Y 4 := Y 2 +( x ′ + e m ) ⊗ z ′ + F ◦ σ + e m ⊗ e m

## 3.1 YES Case

Let y v ⊗ y v for v ∈ V and x u ⊗ x u for u ∈ U be a perfectly satisfying labeling of the label cover instance. That is, for every ( u, v ) ∈ E,π u,v ( y v ⊗ y v ) = x u ⊗ x u . Such a labeling is guaranteed by the YES instance of label cover, with the additional property that the m th coordinate of y v is 1 . Consider the following 2 -coloring of G : for each v ∈ V , A v ( X ) := 〈 X,y v ⊗ y v 〉 . Note that such a function is constant over cosets of H v . Let

$$x _ { 1 } & \coloneqq \langle X _ { 1 }, \overline { y } _ { v } \otimes \overline { y } _ { v } \rangle & x _ { 2 } & \coloneqq \langle X _ { 2 }, \overline { y } _ { v } \otimes \overline { y } _ { v } \rangle \\ y _ { 1 } & \coloneqq \langle Y _ { 1 }, \overline { y } _ { w } \otimes \overline { y } _ { w } \rangle & y _ { 2 } & \coloneqq \langle Y _ { 2 }, \overline { y } _ { w } \otimes \overline { y } _ { w } \rangle$$

and f := 〈 F, x u ⊗ x u 〉 . Note that 〈 F ◦ π u,v , y v ⊗ y v 〉 = 〈 F, π u,v ( y v ⊗ y v ) 〉 = 〈 F, x u ⊗ x u 〉 , and 〈 e m ⊗ e m , y v ⊗ y v 〉 = 〈 e m , y v 〉 = 1 . Using these, the assignments to the 8 query locations are:

$$\Lambda _ { \Lambda v } \cdot \Lambda _ { \Lambda v ^ { \prime } } \quad \Lambda _ { \Lambda \Lambda v ^ { \prime } } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \Lambda _ { \Lambda } \quad \langle \overline { y } _ { v }, \overline { x } \rangle \langle \overline { y } _ { v }, \overline { y } \rangle + f \\ x _ { 1 } & & x _ { 2 } & & x _ { 2 } + ( \langle \overline { y } _ { v }, \overline { x } \rangle + 1 ) \langle \overline { y } _ { v }, \overline { z } \rangle + f \\ y _ { 1 } & & y _ { 1 } + \langle \overline { y } _ { w }, \overline { x } ^ { \prime } \rangle \langle \overline { y } _ { w }, \overline { y } ^ { \prime } \rangle + f + 1 \\ y _ { 2 } & & y _ { 2 } + ( \langle \overline { y } _ { w }, \overline { x } ^ { \prime } \rangle + 1 ) \langle \overline { y } _ { w }, \overline { z } ^ { \prime } \rangle + f + 1 \\ \text{to see at least one of the 4 rows are always not equal. Hence $A$ is a valid 2-color}$$

It is easy to see at least one of the 4 rows are always not equal. Hence A is a valid 2 -coloring of G .

## 3.2 NOCase

Suppose the reduction was applied to a NO instance of label cover. Let k and δ be the parameters specified by Theorem 2.2.

Lemma 3.1. If there is an independent set in G of relative size s then

$$s ^ { 8 } \leq \delta + \frac { 1 } { 2 ^ { k / 2 + 1 } }.$$

Proof. The proof of the lemma is similar to Section 8.2 in Khot and Saket [KS14]. Consider any set A ⊆ V of fractional size s . For every v ∈ V , let A v : F m m × 2 →{ 0 1 , } be the indicator function that is extended such that it is constant over cosets of H v . A is an independent set if and only if

$$\Theta \coloneqq \mathbb { E } _ { u, v, w } \mathbb { E } _ { X _ { i }, Y _ { i } \in \mathcal { T } _ { 2, 8 } } \, \prod _ { i = 1 } ^ { 4 } A _ { v } ( X _ { i } ) A _ { w } ( Y _ { i } ) = 0. \\. \pi \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \ dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots.$$

Now we do the Fourier expansion and take expectations over X ,X ,Y ,Y 1 2 1 2 to obtain the following:

$$\text{Now we do the Fourier expansion and take expectations over } X _ { 1 }, X _ { 2 }, Y _ { 1 }, Y _ { 2 } \text{ to obtain the follow-} \\ \text{ing} ; \\ \Theta = \underset { \substack { \mathbb { E } _ { n } \\ \sigma _ { 1 }, \alpha _ { 2 } \in \mathbb { F } _ { 2 } ^ { m } x \cdot \overline { x } } } { \mathbb { E } _ { f _ { \mathcal { S }, \mathcal { X } } } } \left [ \underset { \substack { \mathbb { E } _ { y } \\ \sigma _ { 1 } } } { \mathbb { E } _ { y } } \left [ \underset { \substack { \mathbb { E } _ { y } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left ( \overline { x } \right ) ^ { 2 } \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { y } \\ \sigma _ { 1 } } } { \mathbb { E } _ { y } } \left [ \underset { \substack { \mathbb { E } _ { y } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } } { \mathbb { E } _ { z } } \left [ \text{$\Gamma_{n}$} } \right ] \text{$\chi_{\beta_{1}$} } \right ] \chi_{\beta_{2}$} \left ( \text{$\Gamma$} \circ \right ) \chi_{\beta_{2}$} \left ( \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } \circ \overline { x } \right ) } \right ] \chi_{\beta_{2}$} \left ( \text{$\Gamma$} \circ \right ) \chi_{\beta_{2}$} \left ( \underset { \substack { \mathbb { E } _ { z } \\ \sigma _ { 1 } } \circ \overline { x } \right ) } \right ] \\ \text{Note that since } F \in \mathbb { F } _ { 2 } ^ { r \times r } \text{ is chosen uniformly at random,} \\ \mathbb { E } \, \chi _ { \alpha _ { 1 } } ( F \circ \pi ) \chi _ { \alpha _ { 2 } } ( F \circ \pi ) \chi _ { \beta _ { 1 } } ( F \circ \sigma ) \chi _ { \beta _ { 2 } } ( F \circ \sigma ) = \mathbb { E } ( - 1 ) ^ { ( \pi ( \alpha _ { 1 } + \alpha _ { 2 } ), F ) + ( \sigma ( \beta _ { 1 } + \beta _ { 2 } ), F ) }$$

Note that since F ∈ F r × r 2 is chosen uniformly at random,

$$\frac { \mathbb { E } } { F } \chi _ { \alpha _ { 1 } } ( F \circ \pi ) \chi _ { \alpha _ { 2 } } ( F \circ \pi ) \chi _ { \beta _ { 1 } } ( F \circ \sigma ) \chi _ { \beta _ { 2 } } ( F \circ \sigma ) = \frac { \mathbb { E } ( - 1 ) ^ { \langle \pi ( \alpha _ { 1 } + \alpha _ { 2 } ), F \rangle + \langle \sigma ( \beta _ { 1 } + \beta _ { 2 } ), F \rangle } } { }$$

is zero unless π α ( 1 + α 2 ) = σ β ( 1 + β 2 ) . Let ν α ( ) := ( -1) 〈 α,e m ⊗ e m 〉 . Now taking expectations over x, y, z, x , y , z ′ ′ ′ , and noting that 〈 α, x ⊗ 〉 y = 〈 αx,y 〉 , we obtain

$$\cdots \cdots \cdots \mp \cdots \cdots \cdots \\ \text{Term} _ { u, v, w } ( \alpha _ { 1 }, \alpha _ { 2 }, \beta _ { 1 }, \beta _ { 2 } ) = ( - 1 ) ^ { \nu ( \beta _ { 1 } + \beta _ { 2 } ) } \widehat { A } _ { v } ( \alpha _ { 1 } ) ^ { 2 } \widehat { A } _ { v } ( \alpha _ { 2 } ) ^ { 2 } \widehat { A } _ { w } ( \beta _ { 1 } ) ^ { 2 } \widehat { A } _ { w } ( \beta _ { 2 } ) ^ { 2 } \\ \Pr \left [ \alpha _ { 1 } \overline { x } = 0 \wedge \alpha _ { 2 } \overline { x } = \alpha _ { 2 } e _ { m } \right ] \cdot \\ \Pr \overline { x } ^ { \prime } \left [ \beta _ { 1 } \overline { x } ^ { \prime } = 0 \wedge \beta _ { 2 } \overline { x } ^ { \prime } = \beta _ { 2 } e _ { m } \right ]$$

when π α ( 1 + α 2 ) = σ β ( 1 + β 2 ) and 0 otherwise. Define:

$$\sum _ { \substack { \cdot \cdot \\ \cdot \cdot \cdot \cdot \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon } }$$

$$\text{when $\pi(\alpha_{1}+\alpha_{2})=\sigma(\beta_{1}+\beta_{2})$ and $0$ otherwise. Define} \colon \\ \Theta _ { 0 } & = \mathbb { E } _ { u, w } \sum _ { \substack { \text{rank}(\alpha_{1}+\alpha_{2}),rank(\beta_{1}+\beta_{2})\leq k \\ \pi(\alpha_{1}+\alpha_{2})=\sigma(\beta_{1}+\beta_{2}) \\ \nu(\beta_{1}+\beta_{2})=0 } } \text{Term} _ { u, v, w } ( \alpha_{1}, \alpha_{2}, \beta_{1}, \beta_{2}) \\ \Theta _ { 1 } & = \mathbb { E } _ { u, w, w } \sum _ { \substack { \text{rank}(\alpha_{1}+\alpha_{2}),rank(\beta_{1}+\beta_{2})\leq k \\ \pi(\alpha_{1}+\alpha_{2})=\sigma(\beta_{1}+\beta_{2}) \\ \nu(\beta_{1}+\beta_{2})=1 } } \text{Term} _ { u, v, w } ( \alpha_{1}, \alpha_{2}, \beta_{1}, \beta_{2}) \\ \Theta _ { 2 } & = \mathbb { E } _ { u, w, w } \sum _ { \max \{ \text{rank}(\alpha_{1}+\alpha_{2}),rank(\beta_{1}+\beta_{2})\}>k \\ \pi(\alpha_{1}+\alpha_{2})=\sigma(\beta_{1}+\beta_{2}) } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text { } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text` \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{} \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{
\text{lower bound $\Theta_{0}$ by $s^{\8}, \, \,upper bound | \Theta_{1} | \text{ by $\delta$ and $| \Theta_{2}| \text{ by $1/2^{k/2+1}$ below.  Along with $(3.1),}$$

We lower bound Θ 0 by s 8 , upper bound | Θ 1 | by δ and | Θ 2 | by 1 2 / k/ 2+1 below. Along with (3.1), this will prove Lemma 3.1.

## 3.2.1 Lower bound on Θ 0

Note that all terms in Θ 0 are positive. Now consider the term corresponding to α 1 = α 2 = β 1 = β 2 = 0 .

## 3.2.2 Upper bound on | Θ 1 |

$$\Phi _ { u, v, w } ^ { \cdot } \widehat { A } _ { v } ^ { 4 } ( 0 ) \widehat { A } _ { w } ^ { 4 } ( 0 ) = \mathbb { E } _ { u } \left ( \mathbb { E } _ { v } \widehat { A } _ { v } ^ { 4 } ( 0 ) \right ) ^ { 2 } \geq \left ( \mathbb { E } _ { u v } \widehat { A } _ { v } ( 0 ) \right ) ^ { 8 } \geq s ^ { 8 }. \\ \text{per bound on } | \Theta _ { 1 } |$$

We can upper bound | Θ 1 | by

$$\iota _ { P P } & \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \iota _ { \i i _ { \iota _ { \iota _ { \iota _ { \iota _ { \i i _ { \iota _ { \iota _ { \iota _ { \iota _ { \i i _ { \i i _ { \iota _ { \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i. i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \ i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \j i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \ j i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \sigma _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ { \i i _ \i i _ { \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \i i _ \j i } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } \ } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } _ } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } { } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }. } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } ) } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } \\ } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }, } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } ( } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }$$

Consider the following strategy for labeling vertices u ∈ U and v ∈ V . For u ∈ U , pick a random neighbor v , choose ( α , α 1 2 ) with probability ̂ A 2 v ( α 1 ) ̂ A 2 v ( α 2 ) and set its label to π α ( 1 + α 2 ) . For w ∈ V , choose ( β , β 1 2 ) with probability ̂ A 2 w ( β 1 ) ̂ A 2 w ( β 2 ) and set its label to β 1 + β 2 . Since A w is folded, both β 1 and β 2 are symmetric and satisfies C v . Since these constraints are homogeneous, β 1 + β 2 is also symmetric and satisfies C v . Also π maps symmetric matrices to symmetric matrices. Note that (3.7) gives the probability that a random edge ( u, w ) of the label cover is satisfied by this labeling. Hence (3.7) and | Θ 1 | are upper bounded by δ .

## 3.2.3 Upper bound on | Θ 2 |

Note that if the rank( α ) &gt; k , for any fixed b , Pr [ x αx = b ] ≤ 1 2 / k +1 . All terms in Θ 2 has max rank( { α 1 ) , rank( α 2 ) , rank( β 1 ) , rank( β 2 ) } &gt; k/ . 2 From (3.2) we have that, for any fixed choice of u, v, w each term in Θ 2 has absolute value at most 1 2 / k/ 2+1 . Since A,B are { 0 1 , } valued functions, sum of their squared coefficients is upper bounded by 1 (i.e. Parseval's inequality). Thus | Θ 2 | ≤ 1 2 / k/ 2+1 .

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0262v4-figure-a5297f41-f7d0-4034-b8c2-3c3e022313a6.jpg)

Proof of Theorem 1.1. We already saw in Section 3.1 that an YES instance of label cover is mapped to a 2 -colorable hypergraph. Since k = (log N ) 1 8 / -2 /epsilon1 and δ = 2 -(log N ) 1 / 4 -2 /epsilon1 , s ≤ 2 -(log N ) 1 / 8 -3 /epsilon1 . Also the number of vertices in G ,

$$n \leq N 2 ^ { m ^ { 2 } } \leq N \cdot 2 ^ { ( \log N ) ^ { 1 0 / 4 + 2 \epsilon } }.$$

From Lemma 3.1 and above, a NO instance of label cover is mapped to a hypergraph G that has no independent set of relative size 2 -(log n ) 1 / 20 -4 /epsilon1 .

## 4 4 -colorable 4 -uniform hypergraphs

In this section, we modify the reduction in the previous section, so that the uniformity of the hypergraph produced is decreased to 4 at the cost of increasing the number of colors required in the YES case to 4 . This method was proposed by Guruswami et. al. [GHH 14]. The hypergraph + G = ( V E , ) constructed will have vertices

$$\mathcal { V } = V \times \left ( \mathbb { F } _ { 2 } ^ { m \times m } \times \mathbb { F } _ { 2 } ^ { m \times m } / \mathcal { H } _ { v } \times \mathcal { H } _ { v } \right ). \\ \text{be expressed as a collection of functions}$$

Any 4 -coloring of G can be expressed as a collection of functions

$$\Phi \times \mathcal { G } \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \tan \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \ sin \, \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \ sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \ cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \osigma \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \lesstharpo \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sec \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \loss \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \exp \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \prod \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \end{}$$

Wecan uniquely extend such functions to get A v : F m m × 2 × F m m × 2 →{ 0 1 , } 2 which is constant over cosets of H ×H v v . This ensures that A satisfies the following: if α = ( α , α 1 2 ) ∈ F m m × 2 × F m m × 2 is such that ̂ A α ( ) is non-zero, then α , α 1 2 are both symmetric and satisfies C v . The set of edges E will be defined by the test mentioned below.

## 4 -Colorable 4 -Uniform Test

- 1. Sample v, w and { X , Y i i } 4 i =1 from the distribution T 2 8 , as described by the test in the previous section.
- 2. Accept if and only if the following 4 values are not all equal :

$$\ A _ { v } ( X _ { 1 }, X _ { 2 } ) \ A _ { v } ( X _ { 3 }, X _ { 4 } ) \ A _ { w } ( Y _ { 1 }, Y _ { 2 } ) \ A _ { w } ( Y _ { 3 }, Y _ { 4 } )$$

## 4.1 YES Case

Given a perfectly satisfying labeling y v ⊗ y v for v ∈ V and x u ⊗ x u for u ∈ U , we define the following 4 -coloring for G : for each v ∈ V ,

$$A _ { v } ( X _ { 1 }, X _ { 2 } ) \coloneqq \left ( \langle X _ { 1 }, \overline { y } _ { v } \otimes \overline { y } _ { v } \rangle, \langle X _ { 2 }, \overline { y } _ { v } \otimes \overline { y } _ { v } \rangle \right ).$$

Note that such a function is constant over cosets of H v . Using the arguments from Section 3.1, it is easy to see that A is a valid 4 -coloring of G .

## 4.2 NOCase

The analysis of the NO case is similar to Section 3.2.

## 5 Acknowledgements

The author would like to thank Prahladh Harsha, Subhash Khot, Rishi Saket and Srikanth Srinivasan for helpful discussions.

## References

[BGH + 12] BOAZ BARAK, PARIKSHIT GOPALAN, JOHAN H ˚ ASTAD, RAGHU MEKA, PRASAD RAGHAVENDRA, and DAVID STEURER. Making the long code shorter . In Proc. 53 th IEEE Symp. on Foundations of Comp. Science (FOCS) , pages 370-379. 2012. arXiv:1111.0405 doi:10.1109/FOCS.2012.83 , .

[BGS98]

MIHIR BELLARE, ODED GOLDREICH, and MADHU SUDAN. Free bits, PCPs, and nonapproximability-towards tight results . SIAM J. Computing, 27(3):804-915, June 1998. (Preliminary version in 36th FOCS , 1995). eccc:TR95-024 doi:10.1137/S0097539796302531 , .

[DG14]

IRIT DINUR and VENKATESAN GURUSWAMI. PCPs via low-degree long code and hardness for constrained hypergraph coloring . In Proc. 54 th IEEE Symp. on Foundations of Comp. Science (FOCS) , pages 340-349. 2014. eccc:TR13-122 doi:10.1109/FOCS.2013.44 , .

+

[GHH 14] VENKAT GURUSWAMI, PRAHLADH HARSHA, JOHAN H ˚ ASTAD, SRIKANTH SRINIVASAN, and GIRISH VARMA. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes . In Proc. 46 th ACM Symp. on Theory of Computing (STOC) , pages 614-623. 2014. arXiv:1311.7407 , doi:10.1145/2591796.2591882 .

[GHS00]

V. GURUSWAMI, J. HASTAD, and M. SUDAN. Hardness of approximate hypergraph coloring . In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on , pages 149-158. 2000. doi:10.1109/SFCS.2000.892074 .

[KS14]

SUBHASH KHOT and RISHI SAKET. Harndess of coloring 2-colorable 12-uniform hypergraphs . In Proc. 55 th IEEE Symp. on Foundations of Comp. Science (FOCS) . 2014. (To appear). eccc:TR14-051 .
Girish Varma
Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions
In a recent result, Khot and Saket [FOCS 2014] proved the quasi-NP-hardness
of coloring a 2-colorable 12-uniform hypergraph with $2^{(\log n)^{\Omega(1)}}$
colors. This result was proved using a novel outer PCP verifier which had a
strong soundness guarantee. In this note, we show that we can reduce the arity
of their result by modifying their 12-query inner verifier to an 8-query inner
verifier based on the hypergraph coloring hardness reductions of Guruswami et.
al. [STOC 2014]. More precisely, we prove quasi-NP-hardness of the following
problems on n-vertex hypergraphs.
  - Coloring a 2-colorable 8-uniform hypergraph with $2^{(\log n)^{\Omega(1)}}$
colors.
  - Coloring a 4-colorable 4-uniform hypergraph with $2^{(\log n)^{\Omega(1)}}$
colors.