On the Hardness of $4$-to-$1$ Games with Perfect Completeness

1 Introduction

• The PCP and Fourier-analysis recipe has produced strong hardness results, but appears unable to establish optimal results for many problems.The introduction highlights 3-coloring as a problem for which algorithms have been studied extensively and the stated best-known hardness result was for k = 5.Source: §1 · p. 4

1.1 Label-Cover, Unique Games and d-to-1 Games

• Perfect completeness matters for hardness applications such as graph coloring, while the cited 2-to-1 games result achieved only almost-perfect completeness.The earlier result established hardness for Gap-2-to-1_r(1 − ε, ε); the paper notes that the distinction from perfect completeness is significant.Source: §1.1 · p. 5

1.2 Main Result

• For every ε > 0, Gap-4-to-1_r(1, ε) is NP-hard for some positive integer r.This establishes the 4-to-1 Games Conjecture for d = 4 and d′ = 1.Source: §1.2 · p. 5

1.2.1 Implications

• For every k ≥ 3, it is NP-hard to distinguish 3-colorable graphs from graphs that are not k-colorable.For every δ > 0, it is also NP-hard to distinguish 2-colorable 3-uniform hypergraphs from those with no independent set of relative size at least δ.Source: §1.2.1 · p. 6

1.3 Our Techniques

• The outer PCP uses quadratic equations for perfect completeness, and a middle PCP applies low-rank tests to convert them into linear equations for the inner PCP.That linearization destroys the covering property needed for composition with a Grassmann-based inner PCP.Source: §1.3 · p. 7
• Lazy parallel repetition creates room for covering properties while preserving soundness, and the inner PCP combines standard and low-rank Grassmann graphs.The covering property from lazy repetition is still insufficient for composition with the Grassmann agreement test, motivating the combined construction.Source: §1.3 · p. 7

2.1.1 The Outer PCP

• Starting from 3LinF2 and applying parallel repetition, the outer PCP has imperfect completeness and soundness at most 2^-Ω_q(βk).Its linear constraints and covering property support the later inner PCP.Source: §2.1.1 · pp. 8–9

2.1 The Imperfect Completeness Construction

• The earlier construction composes an outer PCP with a Grassmann graph gadget to obtain a 2-to-1 game.Its proof must also handle a non-standard soundness guarantee and preserve consistency between the provers' decodings.Source: §2.1.2 · p. 9, §2.1.3 · p. 11

2.1.2 The Inner PCP

• Grassmann encoding makes the composed game essentially 2-to-1 by asking for local linear functions whose restriction must agree, while the covering property supports consistent decoding.The verifier can also enforce the outer PCP's linear equations by checking Alice's encoded answer on a subspace enlarged by the span of their indicator vectors.Source: §2.1.2 · pp. 9–10

2.1.3 On the Non-Standard Notion of Soundness

• Passing the Grassmann test does not ensure global agreement: a table can pass with probability Ω(ε) yet agree on only o(1) locations with any codeword.Instead, the test yields linear structure inside a nontrivial fraction of constant-dimensional zoom-ins; the advice feature aligns the provers' decoding subspaces.Source: §2.1.3 · pp. 10–11

2.1.4 Difficulties in Achieving Perfect Completeness

• Perfect completeness fails because the construction starts from 3LinF2, while Grassmann encoding supports only linear checks; a stronger encoding must also preserve covering and enable suitable advice.A long code permits nonlinear checks, but the passage identifies covering and the outer PCP's advice feature as additional requirements.Source: §2.1.4 · p. 11

2.2.1 A First Attempt: the Quadratic Grassmann Encoding

• Quadratic Grassmann encoding permits quadratic-equation side checks, but its agreement test need not recover a rank-1 symmetric message and it lacks the covering property.The side checks are incorporated by extending the queried subspace with the span of equation indicator vectors and checking the prescribed values there.Source: §2.2.1 · p. 12
• The quadratic Grassmann tensor test enforces symmetric rank-1 local projections and has 4-to-4 agreement, but its covering property still fails.The test queries assignments on augmented subspaces and checks agreement together with symmetry and rank constraints on the tensor projections.Source: §2.2.1 · pp. 12–13

2.2.2 Variations on the Quadratic Grassmann Encoding

• Sparse expanders can provide covering but lack tensor tests, while high-dimensional-expander cliques allow only local tests that do not ensure globally low-rank encodings.With tests on only one or O(1) cliques, provers can choose a rank-1 vector supported in the tested clique’s neighborhood and answer arbitrarily elsewhere.Source: §2.2.2 · pp. 13–14

2.2.3 A Second Attempt: Three-Step Construction

• The second attempt separates tensor testing from the inner PCP, using the middle PCP for tensor tests and lazy parallel repetition to provide additional covering for the Grassmann agreement test.The tensor test’s Grassmann structure is over F^E rather than F^(E×E), making it compatible with the outer PCP’s covering property.Source: §2.2.3 · p. 14

2.2.4 Our Outer PCP

• The outer PCP starts from quadratic-equation instances whose no-case resists joint satisfaction by any r vectors, then converts answers to low-rank symmetric matrices with limited soundness loss.For every r, the theorem gives an ε such that it is NP-hard to distinguish cases; in the no-case, any r vectors jointly satisfy at most a 1 − ε fraction of equations.Source: §2.2.4 · p. 15

2.2.5 Our Middle PCP

• The middle PCP replaces global rank with local rank-one tests, proves soundness under suitable parameters, then uses lazy repetition to hide the critical challenge and restore covering.Lazy repetition hides the actual challenge among many trivial challenges; the resulting covering property supports the Grassmann-based inner PCP.Source: §2.2.3 · p. 14, §2.2.5 · pp. 16–17
• Lazy repetition improves the covering property, and for t sufficiently large compared to k, its sampling process makes x close to uniform in V(E).The process samples a critical index and a corresponding point, then lifts it by appending zeros in missing coordinates.Source: §2.2.5 · pp. 17–18
• The resulting Ψlazy has perfect completeness, small soundness, local tensor tests, and the covering property.Composition with an appropriate Grassmann-graph variant remains nontrivial, motivating the low-rank encoding in the next step.Source: §2.2.5 · p. 18

2.2.6 Our Inner PCP

• The standard Grassmann encoding requires uniformly random advice vectors needing |Ej|^2 bits per index, beyond the Oq(k) bits available in Ψlazy’s advice.The low-rank Grassmann approach restricts subspaces to low-rank vectors; a Hadamard-code construction (an idea also appearing in [Gol23]) gives subspaces whose vectors have bounded rank.Source: §2.2.6 · pp. 18–19
• The final composition is 4-to-1: for any Alice response, at most four Bob answers can make the verifier accept.It uses low-rank Grassmann encoding for the critical block and ordinary Grassmann encoding for noncritical blocks; the bound follows from two possible extensions in each case.Source: §2.2.6 · pp. 19–20
• To prove soundness, a strategy for Ψfinal with value at least ε yields one for Ψlazy with value at least Ωε(1), using stitched global linear functions.Many successful zoom-outs complicate decoding; the proof stitches functions from different Bob questions onto Alice’s standard Grassmann space, where it can apply ideas from.Source: §2.2.6 · p. 20

3.1 General Notations

• General conventions define F2 linear algebra, Grassmann graphs and distributions, probability notation, and assignment tables whose nil entries always fail agreement tests.The paper also specifies notation for empty sequences.Source: §3.1 · p. 21

3.2 Sub-4-to-1 Games

• For every ε in (0, 1), some alphabet parameter r makes distinguishing sub-4-to-1 games with value 1 from value at most ε NP-hard.The paper states that this relaxation implies its main theorem.Source: §3.2 · p. 22

3.3.1 Approximate Coloring of Hypergraphs

• For each fixed c ≥ 2, it is NP-hard to distinguish 2-colorable 3-uniform hypergraphs from those where every c-coloring leaves at least ε of edges monochromatic, with ε ≥ exp(−exp(O(c^3))).The theorem is a slight strengthening of the cited result.Source: §3.3.1 · p. 22

3.3.2 Grassmann Agreement Test

• Grassmann-test soundness yields a linear function on a large subspace, while equality testing yields an entry value that occurs noticeably often after zoom-ins and zoom-outs.The agreement result is from [EKL23]; the paper uses a slightly different formulation.Source: §3.3.2 · p. 23

3.3.3 List Decoding Bounds

• Only maximal occurring decoding pairs are bounded, since zoom-out spaces can proliferate; sufficiently large collections of fixed-codimension zoom-outs contain a large sunflower.The list-decoding bounds and sunflower result are attributed to.Source: §3.3.3 · pp. 23–24

3.4 Proof Organization

• The proof builds five 2-prover 1-round games: completeness is proved independently for each, whereas each later game's soundness relies on its predecessor.The final Game3 is a sub-4-to-1 game whose completeness and soundness yield Theorem 3.3.Source: §3.4 · p. 25

3.5 Parameter Relations

• The parameter condition packages the constants used in Sections 4–6, with a sufficiently large absolute C that may vary between invocations.The parameter relations are collected in Table 1.Source: §3.5 · pp. 25–26, Table 1 · p. 26

4.1.1 Thinning, and Thinning with Advice

• Conditioned on both advice sequences, the thinned subset remains independent across triples, and each triple is wholly retained with a stated probability lower bound.The proposition establishes this conditional structure for arbitrary fixed advice sequences.Source: §4.1.1 · p. 28
• When the thinning parameter is sufficiently small, the advice distribution Amid conditioned on Ain is close in total variation to uniform.The passage identifies β = o(|E|^-1/2) as a sufficient regime for the stated closeness result.Source: §4.1.1 · p. 28

4.2 Preparation: The NAE Predicate

• For a 2-colorable 3-uniform hypergraph, a linear functional on the repeated vertex set restricts to an NAE-satisfying assignment on every challenge set.The challenge sets are formed by selecting one edge from each of the k disjoint copies; each set is viewed as a collection of triples.Source: §4.1 · p. 27, §4.2 · p. 29

4.2.1 Linear Functionals vs. Bilinear Forms

• An NAE-satisfying symmetric bilinear map has jointly NAE-satisfying functionals in any tensor decomposition, and jointly NAE-satisfying functionals induce an NAE-satisfying bilinear map.For a 2-colorable 3-uniform hypergraph, this yields a rank-1 symmetric bilinear form whose restriction to every challenge set is NAE-satisfying.Source: §4.2.1 · pp. 30–31

4.3 The Equation vs. Variable Game

• The section begins defining Game1a as a 2-prover, 1-round equation-versus-variable game parameterized by k, r, q1, q2, β, and a 3-uniform hypergraph H.The supplied passage introduces the game definition but does not include the verifier’s procedure.Source: §4.3 · p. 31
• For any positive k, nonnegative q1 and q2, β in [0,1], and 2-colorable 3-uniform hypergraph H, the verifier in Game1a[H,k,q1,q2,1,β] accepts with probability 1 under the stated strategies.Source: §4.3 · p. 32
• If every 2r-coloring makes at least an ε fraction of edges monochromatic, the basic Game1a verifier rejects with probability at least ε/3.The bound follows because a monochromatic edge leads to inconsistent answers with probability 1/3.Source: §4.3 · pp. 32–33
• Under Condition 3.12, Game1a is sound when every 4r-coloring makes at least an ε fraction of edges monochromatic, using parallel repetition [Rao11].The advice-bearing repeated game is analyzed before applying the projection-game parallel repetition theorem.Source: §4.3 · pp. 33–34

4.4 From Joint Satisfaction to Bilinear Forms

• Game1b has perfect completeness on 2-colorable 3-uniform hypergraphs using a NAE-satisfying symmetric bilinear form of rank at most 1.Restricting a globally rank-1 form gives consistent prover responses and acceptance probability 1.Source: §4.4 · pp. 34–35
• Game1b soundness follows by converting its rank-r bilinear-form strategy into a Game1a strategy with rank parameter 2r while controlling rank drop.The reduction bounds the probability of good question pairs that fail the rank condition, then uses excellent pairs to obtain consistent answers; the resulting soundness applies under Condition 3.12 and the 4r-coloring assumption.Source: §4.4 · pp. 36–37

5 The Middle PCP

• The section first designs and analyzes Game2a with local tensor checks, then uses lazy parallel repetition to obtain Game2b.Sections 5.1–5.3 cover Game2a; Section 5.4 covers the repetition step.Source: §5 · p. 37

5.1 Preparation: Thinning with Subspaces

• The thinning distribution provides a covering property: a random subspace associated with a β-thinning, lifted to the larger space, is close to uniform even when conditioned on advice.The section also establishes a smoothness property for the thinning distribution: conditioning on advice and the sampled subspace, any set S ⊆ E of size at most 2 is retained with probability at least 1 − 4q1+ℓ+1β.Source: §5.1 · pp. 37–38

5.2 The Local Tensor Check Game

• Game2a checks that Alice’s bilinear form has rank at most 1 on U ⊗ U, while Bob receives a containing subspace U′; it has perfect completeness on 2-colorable 3-uniform hypergraphs.The provers can ignore U and U′ and use a perfect strategy for Game1b. Giving Bob U′ is needed for the final 4-to-1 game, but complicates soundness because genuine cheating strategies exist.Source: §5.2 · pp. 39–40

5.3 Soundness Analysis

• The soundness analysis uses the Grassmann decoding theorem, first turning agreement between Alice’s and Bob’s tables into a condition that Alice’s table passes the Grassmann equality test with noticeable probability.The advice sequence Amid, though irrelevant to Game2a’s verifier, supports the soundness analysis.Source: §5.3.1 · p. 41, §5.3.2 · p. 42

5.3.1 Preparing for Grassmann Decoding

• Lemma 5.15 prepares for decoding by relating Alice–Bob agreement to Alice’s table’s behavior under the Grassmann equality test.The argument considers subspaces U sampled inside a fixed U′ and uses thinning and the distribution of U′ in its analysis.Source: §5.3.1 · pp. 41–42

5.3.2 Invoking the Grassmann Decoding Theorem

• Under Condition 3.12, when the verifier’s conditional acceptance is at least 2^-q2/3, Lemma 5.16 asserts a decoding conclusion including an NAE-satisfying symmetric bilinear map f_A.The supplied passage identifies f_A as a map on FE2, with its existence stated over the conditional distribution given E and Ain.Source: §5.3.2 · pp. 42–43
• Grassmann decoding yields a collection of subspaces Q with associated NAE-satisfying symmetric bilinear maps of rank at most 2q2 + 1.The proof then relates good subspaces to good A responses and establishes that good A responses are abundant.Source: §5.3.2 · pp. 43–44

5.3.3 Deriving Strategy for the Outer PCP

• η-pruning replaces Alice’s response with nil when its verifier success is below η, and drops the provers’ success probability by at most η.This pruning ensures decoded functions retain noticeable consistency with Bob’s table.Source: §5.3.3 · pp. 44–45
• Under Condition 3.12, Game2a has soundness when every 4r-coloring of H leaves at least an ε fraction of edges monochromatic.The proof prunes low-success Alice responses and derives strategies for Game1b from the remaining tables, contradicting its soundness.Source: §5.3.3 · pp. 44–46

5.4 Lazy Parallel Repetition

• Game2b has perfect completeness on 2-colorable 3-uniform hypergraphs when k ≥ ℓ2.It uses lazy parallel repetition with one true challenge block and repeated randomly sampled Alice challenges in the other blocks; advice lists enable the inner PCP and do not hurt soundness.Source: §5.4 · p. 47
• Under the same coloring condition and Condition 3.12, Game2b has soundness, obtained by reducing strategies to Game2a with q2 = 0.The reduction plants the Game2a questions in the critical block and uses shared data for the other blocks, preserving consistency there.Source: §5.4 · p. 48

6.1 Preparation: Tripled Packets

• For each tripled set E, a unique linear map on N(E) satisfies SymNAE conditions, jointly encoding NAE satisfaction and symmetry.The inner PCP framework also combines these side conditions with tensor checks on tripled packets.Source: §6.1 · pp. 49–50

6.1.1 Thinning of Tripled Packets

• The thinning distribution makes packet subspaces U1, …, Ut mutually independent and jointly independent of the randomly chosen critical index.The critical coordinate is the block containing the planted true challenge in Game2b.Source: §6.1.1 · pp. 50–51

6.2 Preparation: Low-Rank Grassmann

• For any subspace W of small codimension, low-rank Grassmann subspaces lie inside W with probability approximately matching the full Grassmann graph.The paper notes that spectral expansion of the low-rank Grassmann graph is not used.Source: §6.2 · p. 51

6.2.1 Construction from Hadamard Code

• The Hadamard-based construction yields subspaces of dimension at most ℓ whose vectors all have low rank, rather than being uniformly distributed among Grassmann subspaces.When the input vectors are generic, each nonzero vector has the maximum rank allowed by this construction.Source: §6.2.1 · p. 52

6.2.2 Mixed-Type Advice Sequences

• The mixed advice sequences pair low-rank Grassmann structure on potentially critical coordinates with standard Grassmann structure on noncritical coordinates.Critical-coordinate advice uses vectors from the base space and is saturated when its specified even-indexed vectors are linearly independent; noncritical-coordinate vectors are arbitrary.Source: §6.2.2 · pp. 52–53
• Mixed-type advice sequences span low-rank Hadamard vectors on critical blocks and generic vectors elsewhere; truncating advice to q0 coordinates spans a corresponding subspace.Source: §6.2.2 · pp. 53–54

6.2.3 Zoom-out Probabilities

• Conditioned on fixed sub-advice, random extensions mimic Grassmann-subspace containment probabilities, including extensions from q0 to ℓ dimensions when s ≥ ℓ + w.Source: §6.2.3 · pp. 55, 57

6.2.4 Mixed-Type Grassmann Graph

• Independent advice sequences span actual ℓ-dimensional subspaces, inducing a mixed-type Grassmann graph; under the stated block-size assumption, conditioned spans are close in total variation to uniform compatible subspaces.Source: §6.2.4 · p. 58
• For valid zoom-in and zoom-out subspaces Q ⊆ W, the fraction of mixed-type Grassmann subspaces containing Q and contained in W behaves similarly to the standard Grassmann domain.Source: §6.2.4 · pp. 58–59
• For mixed-type subspaces, the conditional probability of L ⊆ W given Q ⊆ L is between 2^(-w(ℓ-q0)-2) and 2^(-w(ℓ-q0)+2).Source: §6.2.4 · p. 59

6.2.5 Extension of Agreement

• The extension-of-agreement lemma seeks a larger subspace W′ containing W and a linear function g extending f, under its stated dimension and agreement assumptions.The supplied result passage gives the existence conclusion but omits the guarantee satisfied by g.Source: §6.2.5 · p. 59

6.3 The 4-to-1 Game Construction

• Game3 encodes prover strategies with mixed-type Grassmann subspaces, adjacent in dimension, and adds local tensor tests and side conditions to obtain an at-most-4-to-1 game.The dimension gaps give Bob at most two more bits of freedom than Alice; the text notes this can be converted to an actual 4-to-1 game.Source: §6.3 · pp. 61–62
• Game3 has value 1 when the 3-uniform hypergraph is 2-colorable.The stated completeness proof derives strategies from a proper 2-coloring, under which the verifier accepts with probability 1.Source: §6.3 · pp. 62–63
• Game3 soundness is stated assuming Condition 3.12 and that every 4r-coloring of H has at least an ε fraction of monochromatic edges.The supplied passage omits the lemma’s consequent bound.Source: §6.3 · p. 63

6.4 Overview of Soundness Analysis

• From strategies for Game3 of value at least δ, the overview decodes Alice to a global linear function satisfying side conditions and tensor tests, then uses an extension lemma to decode Bob.The mixed-type subspace distribution is close to uniform by a covering property, supporting Alice’s decoding; Alice and Bob’s spaces differ by one dimension, motivating the extension step.Source: §6.4 · pp. 63–64
• The analysis bypasses bounding Bob’s decoding list: consistency across many Bob-packets yields noticeable agreement between Alice’s and Bob’s responses.It seeks a Bob decoding, or its linear extension, consistent with Alice’s table in the ordinary rather than mixed-type Grassmann domain.Source: §6.4 · p. 64

6.5.1 Notations

• Notation 6.34 defines Din as the verifier-sampled joint distribution of (E, U, E′, U′, A) in Game3[H, k, ℓ1, ℓ2, t, s, β], with Q := σ(A[q0]), L := σ(A[ℓ1]), and L′ = σ(A[ℓ1+1]).Source: §6.5.1 · pp. 64–65

6.5.2 Covering Property of Mixed-Type Subspaces

• Under Condition 3.12, for each fixed Alice-packet (E, U) and positive integer ℓ ≤ 2ℓ1, sampling from Din conditioned on (E, U) yields σ(A[ℓ]) within t−1/4 total variation of uniform on Gr(V(E), ℓ).Here, Q is smooth with respect to (E, U) when dim Q = q0 and TVDE,U(Q) ≤ t−1/8.Source: §6.5.2 · p. 68

6.5.3 Alice’s Existence of Decoding

• If Alice’s and Bob’s tables agree with noticeable probability, then Alice can use her zoom-in Q, with noticeable probability, to come up with a global linear function f agreeing.Source: §6.5.3 · p. 70

6.5.4 Bob’s Existence of Decoding

• With 2^-q0-transferable tables and a smooth zoom-in, Alice’s consistent global linear function implies that, on average over Bob’s challenge, Bob has a global function making his question pre-answerable.The result is stated under Condition 3.12 and the lemma’s assumptions for the fixed Alice-packet and subspace Q.Source: §6.5.4 · p. 71
• Under Proposition 6.55’s hypotheses, a pre-answerable Bob-packet with its subspace is answerable.The proposition assumes Condition 3.12 and 2^-q0-transferability, in addition to its stated packet and subspace conditions.Source: §6.5.4 · p. 73
• The conversion uses distributions of Bob’s subspace that remain close in total variation after conditioning on containment in any subspace of codimension at most q0.The cited proof gives bounds of k^-2 before the further conditioning and k^-1 afterward, enabling pre-answerability to imply answerability.Source: §6.5.4 · p. 73
• An Alice-packet with verification probability at least 2^-q0/3 yields a Bob-packet and zoom-in that are answerable with noticeable probability, assuming Condition 3.12 and 2^-q0-transferability.This is the conclusion of Lemma 6.56.Source: §6.5.4 · p. 73

6.6 Soundness Analysis

• Pruning the unfolded tables yields 2^-q0-transferable F and G while retaining agreement at least δ/2 from an initial agreement above δ.Pruning decreases agreement by at most 2^-q0+1.Source: §6.6 · p. 75

6.6.1 Good tuples and excellent tuples

• Goodness checks Bob’s answerability and agreement on his smaller mixed-type domain; excellence instead requires extending Bob’s pair to a viable Alice-list response.This extension may require shrinking the zoom-in set or enlarging the zoom-out subspace.Source: §6.6.1 · pp. 76–77

6.6.2 A Lower Bound on the Fraction of Good Tuples

• Good tuples occur with noticeable probability, and the analysis establishes that excellent tuples occur with non-negligible probability.The proof of the excellent-tuple probability is deferred to Section 6.7.Source: §6.6.2 · pp. 77, 79

6.6.3 Completing the Soundness Analysis

• On an excellent tuple, the induced strategy wins with non-negligible probability.The strategy's success analysis uses compatible Alice and Bob responses on that tuple.Source: §6.6.3 · p. 79
• Under Condition 3.12, the strategy wins with probability at least exp(-3Cq_0^2ℓ_1), contradicting Lemma 5.22.The bound follows by combining the preceding probability estimates and Claims 6.62 and 6.63.Source: §6.6.3 · p. 80

6.7 Proof of Claim 6.62

• There exist a subspace W of V(E) with codimension at most 2q0, a subspace Q′ of Q with codimension at most 1, and a linear map f: W→F2 such that, for some i∈[m], Wi⊆W and f|Wi=fi.Source: §6.7 · p. 81
• For the coordinate set C_{E,U,Q}, |C_{E,U,Q}| ≤ 3k·exp(1000k^5); combining Claim 6.61 with a union bound yields Claim 6.62 as a direct corollary.Source: §6.7 · p. 81

6.8 Proof of Lemma 6.64

• A sunflower of Bob subspaces enables a Grassmann linearity test whose noticeable passing probability yields an Alice decoder, and list decoding forces agreement with some Bob decoder f_i.Good packets provide local agreement; inclusion-exclusion transfers this to global test passing. The proof notes that mixed-Grassmann calculations are technically trickier than standard Grassmann calculations.Source: §6.8 · p. 83
• For E,U,W,Q′, agree(E,U,W,Q′) is at least P_(L1,L2)∼P[ F[E,U,L1]|L1∩L2 = F[E,U,L2]|L1∩L2 ] − exp(−Ω(k)).Source: §6.8 · p. 89
• A variant of the list-decoding result from yields a linear function and index whose function satisfies Equation (6.32) and agrees with fij on Wij.The proof uses the list of linear functions satisfying Equation (6.32) to establish this consistent decoding.Source: §6.8 · pp. 89–91

A Basic Linear Algebra

• Restricting a bilinear form to U⊗U loses at most 2 codim U in rank.The proof bounds the rank loss from composing with the embedding on the right and its adjoint on the left by codim U each.Source: A Basic Linear Algebra · p. 95
• If restricting f to U⊗U preserves its rank, then every vector in the image of Tf restricts to a vector in the image of the restricted form’s map.This is stated equivalently as h|U belonging to image(Tg) for each h in image(Tf).Source: A Basic Linear Algebra · p. 96
• For a symmetric bilinear form of rank r, some coordinate subset of size r preserves rank r when the form is restricted to that subset.The appendix establishes this through Corollary A.3.Source: A Basic Linear Algebra · p. 96
• Every symmetric bilinear form of rank r has a tensor decomposition using at most 3r/2 linear functionals.The appendix notes that this decomposition is also used in Lemma 4.26.Source: A Basic Linear Algebra · p. 96
• If rank(f) is at least 2 + 2 codim W, restricting to W⊗W leaves rank at least 2, and a sufficiently large random subspace usually retains rank above 1.Lemma A.5 assumes Q ⊆ W and q + 2 ≤ ℓ ≤ dim W; it samples U of dimension ℓ containing Q.Source: A Basic Linear Algebra · pp. 98–99

B From Sub-4-to-1 to Exact 4-to-1 Games

• For ε ∈ (0, 1), the reduction maps GapS-4-to-1_r(1, ε/2) to Gap-4-to-1_r′(1, ε), with k = ⌈4/ε⌉ and r′ = kr.This is the reduction used to derive the exact theorem from the sub-4-to-1 result.Source: B From Sub-4-to-1 to Exact 4-to-1 Games · p. 99
• The new game keeps the original constraint graph, enlarges each alphabet with a Z/kZ coordinate, and replaces each edge constraint with k constraints.The total number of new constraints is k|E|.Source: B From Sub-4-to-1 to Exact 4-to-1 Games · p. 99
• For each edge, the construction partitions the left alphabet into four-symbol blocks and the right alphabet into singleton blocks to form 4-to-1 constraints.The block construction uses subsets ΓL,i and ΓR,i for each paired block.Source: B From Sub-4-to-1 to Exact 4-to-1 Games · p. 99
• If the original game has value 1, assignments satisfying every original constraint yield completeness for the constructed game.Conversely, when an original edge is violated, at most two of its k new constraints can be satisfied by the transformed assignments.Source: B From Sub-4-to-1 to Exact 4-to-1 Games · p. 100

Theorem 3.4

• For each fixed c≥2, it is NP-hard to distinguish 2-colorable 3-uniform hypergraphs from those where every c-coloring makes at least ε fraction of edges monochromatic, for ε≥exp(−exp(O(c^3))).This is Theorem 3.4.Source: C Approximate Coloring of Hypergraphs · p. 101

Proof construction

• The reduction starts from (3u, 5u)-biregular label cover with alphabets 7u and 2u, perfect completeness, and no-case value at most 2^-γu.The label-cover hardness follows by applying the PCP theorem [ALM+98, AS98] and parallel repetition to the equation-vs.-variable game for 3SAT5 instances.Source: C Approximate Coloring of Hypergraphs · p. 101
• The proof builds a multi-layered label-cover instance, then composes it with a Kneser-graph-based inner gadget to construct the hypergraph.The proof has eight steps; all but Step 6 are nearly identical to.Source: C Approximate Coloring of Hypergraphs · pp. 101–102

Completeness

• When the label-cover instance has value 1, the constructed hypergraph is 2-colorable.A satisfying assignment induces lifted assignments in each layer, which define the two-coloring and ensure no hyperedge is monochromatic.Source: C Approximate Coloring of Hypergraphs · p. 103

Soundness

• For soundness, the proof selects a common leading color across layers, retains a critical layer-pair set E* of size at least |Ei,j|/(4c^2), and uses it to decode assignments.The decoding proceeds from the coloring to assignments for the critical layers and then to correlated assignments for the original label-cover instance.Source: C Approximate Coloring of Hypergraphs · pp. 103–106

C Approximate Coloring of Hypergraphs

• A deterministic instantiation of (A0, A1) satisfies at least η/(4c3) of the constraints in Ψ.The existence follows from the random-pair argument described in the passage.Source: C Approximate Coloring of Hypergraphs · p. 106
• For |R| ≥ 6c and |R|/3 ≤ r ≤ 2|R|/3, the lemma gives an element of R with a stated incidence guarantee when few r-element subsets avoid every B_i.It assumes each B_i ⊆ R has size at most c; the supplied passage does not include the incidence threshold.Source: C Approximate Coloring of Hypergraphs · p. 106

D Grassmann Decoding Theorems

• The appendix derives the paper's Grassmann decoding theorems from versions in the literature that differ slightly.It addresses Theorems 3.5 and 3.6.Source: D Grassmann Decoding Theorems · p. 107
• The derivation concerns Theorems 3.5 and 3.6.These are the Grassmann decoding theorems used in the paper.Source: D Grassmann Decoding Theorems · p. 107
• The appendix's role is to bridge the paper's theorem versions to the slightly different existing-literature versions.The passage describes how those theorems can be derived from the literature results.Source: D Grassmann Decoding Theorems · p. 107

D.1 The Expansion Theorem

• Small vertex sets may fail to expand well in the Grassmann graph, so the approach considers sets that remain small after zoom-ins and zoom-outs.This motivates the section's pseudorandom-set framework.Source: §D.1 · p. 107
• The short-code graph lifts the Grassmann graph to a Cayley graph over the matrix additive group, generated by rank-1 matrices.The lift is used to facilitate Fourier analysis.Source: §D.1 · p. 108
• A Grassmann set L is encoded by an indicator on matrices that selects full-rank X whose column space belongs to L; (q, ε)-pseudorandomness transfers to (q, 4ε)-pseudorandomness.The transfer is stated for n−q ≥ ℓ ≥ q+1.Source: §D.1 · p. 108
• The cited main expansion theorem states that pseudorandom sets have good expansion in the short-code graph.The section then transfers this expansion theorem to the Grassmann graph.Source: §D.1 · p. 108

• The section uses an argument due to [BKS19] to deduce decoding from expansion.The decoding conclusion is expressed through failure of pseudorandomness for a set of subspaces.Source: §D.2 · pp. 109–110
• Theorem 3.5 gives conditions under which a table yields subspaces and a linear map with the stated containment and agreement properties.Its parameter range requires n − q − 3 ≥ ℓ ≥ q + 3.Source: §D.2 · p. 110
• Lemma D.8 states that a table locally constant on Grassmann-graph edges is globally constant within some zoom-in/zoom-out combination.The lemma concerns a finite-valued table that may also contain nil entries.Source: §D.2 · p. 111
• Theorem 3.6 is a variant of the local-constancy result that requires abundant zoom-ins.The proof is described as analogous to using Lemma D.8 to prove Theorem 3.5.Source: §3.3.2 · p. 23, §D.2 · pp. 111–112

• The cited linearity lemma applies when n ≥ 2ℓ and 40 ≤ b ≤ ℓ/4, and yields a linear map from the table under its stated hypothesis.The cited statement specifies an absolute constant C and a parameter ε in its conclusion.Source: E Linearity Testing and List Decoding… · p. 112
• Lemma E.2 extends a linearity result to tables whose entries may be nil.Its proof fills nil entries randomly, then applies Lemma E.1 to obtain a linear map.Source: E Linearity Testing and List Decoding… · pp. 112–113
• Corollary 6.66 extends the nil-entry result to account for a fixed subspace Q and zoom-ins.The proof reduces to a table on a complementary subspace and translates the conclusion back.Source: §6.8 · p. 85, E Linearity Testing and List Decoding… · pp. 113–114

• The section supplies proofs for covering-property-type statements left unproved in Sections 4 to 6.Source: F Covering Properties · p. 114

• Conditioned on both advice tuples, the sampled set E′ is independent across triples, with each triple entirely included with probability at least the stated bound.Source: §F.1 · p. 114
• For the conditioning analyzed in Proposition 4.7, each triple is entirely included in E′ with probability at least the stated bound.Source: §F.1 · pp. 114–115
• Conditioned on Ain, the marginal distribution of Amid is close to uniform over Alice’s space, as asserted by Proposition 4.8.The proposition gives a total-variation bound in terms of q1, q2, and β.Source: §F.1 · p. 115

F.2 Covering in the Middle PCP

• The middle PCP introduces Jmid by augmenting the thinning-with-advice distribution with a subspace generated using advice vectors.The subspace is formed from the span of Amid and a generated vector sequence.Source: §F.2 · p. 117
• After conditioning on fixed Ain and Amid, Proposition 5.4 bounds the total-variation distance between the resulting U distribution and a uniform distribution.The proposition applies to fixed advice tuples satisfying the stated dimension condition.Source: §F.2 · p. 117
• Before conditioning on the advice sequences, the marginal distribution of A′ matches the one in Jout, allowing Proposition 4.8 to be applied after conditioning.The conditioning event fixes Ain and Amid.Source: §F.2 · p. 118

F.3 Covering in the Inner PCP

• A general probabilistic fact establishes the covering property achieved by the lazy parallel repetition step.It is stated in a form suitable for the inner PCP.Source: §F.3 · p. 118
• The product distribution is generated by choosing a uniform coordinate, sampling it from its designated distribution, and sampling every other coordinate uniformly.The proposition assumes equal-sized coordinate sets and surjective coordinatewise maps.Source: §F.3 · p. 118
• For outputs in the support of the image distribution, Proposition F.1 considers the conditional input distribution on each map preimage and its distance from uniform.The proposition defines the coordinatewise product map and analyzes conditioning on its output.Source: §F.3 · pp. 118–119