Introduction
A permutation constraint prescribes exactly one label at one endpoint for each label at the other. The Unique Games Conjecture asserts that systems of such constraints can be hard to approximate even when almost all constraints can be satisfied. We resolve this conjecture positively, with an explicit unweighted reduction from 3SAT.
The theorem
A Unique Games instance has a finite vertex set, a finite alphabet K K K e = ( u e , v e , π e ) e=(u_e,v_e,\pi_e) e = ( u e , v e , π e ) π e \pi_e π e K K K a a a e e e a ( v e ) = π e ( a ( u e ) ) a(v_e)=\pi_e(a(u_e)) a ( v e ) = π e ( a ( u e )) val ( G ) \operatorname{val}(G) val ( G ) explicit and unweighted when the entire vertex and constraint lists are written out, including the table of each permutation. A simple bipartite instance has two disjoint vertex sets and at most one constraint on each pair of opposite vertices.
Theorem 1.1 (Unique Games Theorem). For every fixed ε , δ ∈ ( 0 , 1 / 2 ) \varepsilon,\delta\in(0,1/2) ε , δ ∈ ( 0 , 1/2 ) there are an integer s ≥ 1 s\ge1 s ≥ 1 and a deterministic polynomial-time reduction from 3SAT to explicit unweighted Unique Games instances G φ G_\varphi G φ over K = F 2 s K=\mathbb{F}_2^s K = F 2 s such that
φ satisfiable ⟹ val ( G φ ) ≥ 1 − ε , φ unsatisfiable ⟹ val ( G φ ) ≤ δ . \begin{aligned}
\varphi\text{ satisfiable} &\Longrightarrow\operatorname{val}(G_\varphi)\ge1-\varepsilon,\\
\varphi\text{ unsatisfiable} &\Longrightarrow\operatorname{val}(G_\varphi)\le\delta.
\end{aligned} φ satisfiable φ unsatisfiable ⟹ val ( G φ ) ≥ 1 − ε , ⟹ val ( G φ ) ≤ δ . The graph is simple and bipartite, and every constraint is a translation a ( v e ) = a ( u e ) + c e a(v_e)=a(u_e)+c_e a ( v e ) = a ( u e ) + c e of K K K The alphabet, the degree of the running-time polynomial, and its constants depend only on ε , δ \varepsilon,\delta ε , δ
Thus the result resolves the Unique Games Conjecture positively in its usual edge-value formulation [23 ] . The two errors are prescribed independently, before the alphabet is chosen. Binary translation constraints are a known equivalent formulation of the conjecture [24 ] ; the reduction here produces that form directly.
Theorem 1.1 supplies the Unique Games hypothesis in earlier hardness reductions for cut, covering, constraint-satisfaction, ordering, deletion, and clustering problems [24 , 27 , 36 , 17 , 9 , 10 ] . The reductions and the resulting approximation thresholds are due to those authors. Section 8 gives the precise problem formulations, strict thresholds, and reduction qualifications, together with proofs of the consequences.
Proofs, codes, and the quantifiers
The central difficulty is to retain completeness near one when every label permits only one reply. The earlier connection between proof verification and approximation hardness was developed by Feige, Goldwasser, Lovász, Safra, and Szegedy [15 ] , by Arora and Safra through proof composition [3 ] , and by Arora, Lund, Motwani, Sudan, and Szegedy through the constant-query PCP theorem [2 ] . Bellare, Goldreich, and Sudan introduced the long code and folding for verifier composition [7 ] , Section 3.3. The long code of an answer is the table f ↦ f ( a ) f\mapsto f(a) f ↦ f ( a ) [18 ] .
Khot introduced the Unique Games Conjecture in 2002 and gave an algorithm based on semidefinite rounding [22 ] . Several algorithmic guarantees explain why its order of quantifiers matters. For a fixed target error, Trevisan combines semidefinite rounding with graph decomposition to obtain a polynomial-time guarantee when the input error shrinks at the reciprocal-logarithmic rate in the instance size [41 ] . Charikar, Makarychev, and Makarychev use randomized semidefinite rounding to obtain expected value 1 − O ( ϵ log q ) 1 - O(\sqrt{\epsilon\log q}) 1 − O ( ϵ log q ) q q q 1 − ϵ 1 - \epsilon 1 − ϵ [8 ] ; this guarantee loses accuracy as the alphabet grows, whereas the conjecture permits a large fixed alphabet after the errors are chosen. Kolla’s spectral enumeration gives a running-time bound in terms of the dimension of a suitable spectral subspace of the label-extended graph, whose vertices are variable–label pairs [30 ] . Arora, Barak, and Steurer use spectral decomposition and enumeration to obtain near-satisfying solutions for sufficiently small fixed completeness error, with a guarantee independent of the fixed alphabet size [1 ] ; their running-time bound is subexponential, not polynomial, for fixed positive error. These are distinct limits on the known guarantees.
Integrality gaps concern the strength of a relaxation. Khot and Vishnoi constructed Unique Games with semidefinite value arbitrarily close to one and integral value arbitrarily close to zero, even with triangle inequalities [29 ] . Barak, Gopalan, Håstad, Meka, Raghavendra, and Steurer introduced the short code, based on Reed–Muller codes, as a shorter substitute for the long code in applications including alphabet reduction and quantitative integrality gaps [5 ] . These constructions constrain particular relaxations; a hardness reduction requires a separate argument. Bafna, Barak, Kothari, Schramm, and Steurer obtain polynomial-time constant-value guarantees for nearly satisfiable translation games whose graphs have suitable low-degree sum-of-squares hypercontractivity certificates, including noisy hypercube and noisy Reed–Muller short-code graphs [4 ] . The rank-one matrix shortcode used below is a different graph, and our argument does not assume these certificates.
Grassmann expansion and the completeness obstacle
The closest preceding hardness breakthrough concerns 2-to-1 and 2-to-2 games with imperfect completeness. A 2-to-1 constraint is a projection with exactly two preimages per right label. A 2-to-2 constraint partitions the labels on each side into pairs and matches these pairs bijectively, allowing the four combinations within a matched pair. Khot, Minzer, and Safra’s STOC 2017 work proposed a Grassmann-graph reduction whose nonstandard soundness guarantee was conditional on a structural hypothesis [26 ] . Dinur, Khot, Kindler, Minzer, and Safra’s STOC 2018 work proposed a reduction with ordinary edge-satisfaction soundness, conditional on an agreement hypothesis [12 ] ; their expansion work formulated the relevant structural problem and established partial cases [11 ] . Barak, Kothari, and Steurer connected expansion to the needed agreement test through a binary matrix representation [6 ] . The expansion theorem of Khot, Minzer, and Safra completed this line in 2018 [25 ] .
These results established hardness for almost satisfiable 2-to-1 and 2-to-2 games and, as a consequence, a Unique Games gap with completeness close to one half and arbitrarily small soundness. Obtaining Unique Games completeness arbitrarily close to one was a separate problem.1
The degree-two matrix shortcode of Barak, Kothari, and Steurer [6 ] is the formulation used here: its vertices are binary matrices and its steps add rank-one matrices. Their two-reply rule permits either the old answer or its translate by the update’s left factor; requiring equality alone gives a one-half completeness guarantee. They discussed higher-degree tests as a possible route to improving this completeness [6 ] , Section 1.6. The inverse statement we use, derived from Grassmann expansion, appears in Theorem 5.1. Ellis, Kindler, and Lifshitz later gave a shorter expansion proof using hypercontractivity on spaces of linear maps [14 ] ; our external input remains the Khot–Minzer–Safra theorem. Our proof keeps the established degree-two inverse theorem and changes the noise using a nonlinear map. The following comparison explains that choice.
The construction and proof
The uniform rank-one test illustrates the completeness problem. Let M M M ℓ \ell ℓ m m m z ∈ F 2 m z \in\mathbb{F}_2^m z ∈ F 2 m f z ( M ) = M z f_z(M)=Mz f z ( M ) = M z
f z ( M + a ℓ T ) − f z ( M ) = a ( ℓ T z ) . f_z(M+a\ell^{\mathsf{T}})-f_z(M)=a(\ell^{\mathsf{T}}z). f z ( M + a ℓ T ) − f z ( M ) = a ( ℓ T z ) . For independent uniform a ∈ F 2 ℓ a \in\mathbb{F}_2^\ell a ∈ F 2 ℓ ℓ ∈ F 2 m \ell\in\mathbb{F}_2^m ℓ ∈ F 2 m ( 1 + 2 − ℓ ) / 2 (1+2^{-\ell})/2 ( 1 + 2 − ℓ ) /2
For any prescribed p > 0 p>0 p > 0 ℓ \ell ℓ V \mathcal{V} V K = F 2 ℓ K=\mathbb{F}_2^\ell K = F 2 ℓ C : V → K C:\mathcal{V}\to K C : V → K μ \mu μ V \mathcal{V} V a ∼ μ a\sim\mu a ∼ μ
C ( x + h ) = C ( x ) + h ( h ∈ K ) , Pr [ C ( x + a ) ≠ C ( x ) ] ≤ p C(x+h)=C(x)+h\quad(h\in K),\qquad\Pr[C(x+a)\ne C(x)]\le p C ( x + h ) = C ( x ) + h ( h ∈ K ) , Pr [ C ( x + a ) = C ( x )] ≤ p where x x x a a a K K K a a a 1 / 8 1/8 1/8 p p p ℓ \ell ℓ K K K
For the same nonzero z z z P ∈ Hom ( F 2 m , V ) P\in\operatorname{Hom}(\mathbb{F}_2^m,\mathcal{V}) P ∈ Hom ( F 2 m , V ) P ↦ C ( P z ) P\mapsto C(Pz) P ↦ C ( P z )
C ( P z ) and C ( P z + a ( ℓ T z ) ) C(Pz)\qquad\text{and}\qquad C(Pz+a(\ell^{\mathsf{T}}z)) C ( P z ) and C ( P z + a ( ℓ T z )) under the update P ↦ P + a ℓ T P\mapsto P+a\ell^{\mathsf{T}} P ↦ P + a ℓ T P z Pz P z V \mathcal{V} V a a a ℓ T z \ell^{\mathsf{T}}z ℓ T z p / 2 p/2 p /2
We start the reduction from binary parity equations on three distinct variables. Each equation has four satisfying triples. A table on an equation tuple U = ( e 1 , … , e k ) U=(e_1,\ldots,e_k) U = ( e 1 , … , e k ) V \mathcal{V} V m = 1 + 2 k m=1+2k m = 1 + 2 k K K K [28 ] , while the translation orbits adapt the folding principle of Bellare, Goldreich, and Sudan [7 ] .
For soundness, suppose a labeling passes this test with probability at least 0.99 0.99 0.99 g = ( g i ) i = 0 m ∈ ( V ∗ ) m g=(g_i)_{i=0}^{m}\in(\mathcal{V}^*)^m g = ( g i ) i = 0 m ∈ ( V ∗ ) m ( − 1 ) ∑ i g i ( P e i ) (-1)^{\sum_i g_i(Pe_i)} ( − 1 ) ∑ i g i ( P e i ) e i e_i e i F 2 m \mathbb{F}_2^m F 2 m ℓ \ell ℓ
E a ∼ μ , ℓ ( − 1 ) ∑ i ℓ i g i ( a ) = Pr a ∼ μ [ g i ( a ) = 0 for every i ] , E a u n i f o r m i n K , ℓ ( − 1 ) ∑ i ℓ i g i ( a ) = 2 − dim span { g i ∣ K } . \begin{aligned}
\mathbb{E}_{a\sim\mu,\ell}(-1)^{\sum_i \ell_i g_i(a)}&=\Pr_{a\sim\mu}[g_i(a)=0\text{ for every }i],\\
\mathbb{E}_{a\ \mathrm{uniform\ in}\ K,\ell}(-1)^{\sum_i \ell_i g_i(a)}&=2^{-\dim\operatorname{span}\{g_i|_K\}}.
\end{aligned} E a ∼ μ , ℓ ( − 1 ) ∑ i ℓ i g i ( a ) E a uniform in K , ℓ ( − 1 ) ∑ i ℓ i g i ( a ) = a ∼ μ Pr [ g i ( a ) = 0 for every i ] , = 2 − d i m span { g i ∣ K } . The first multiplier is nonnegative and, by latent detection, is at most 7 / 8 7/8 7/8 K K K V = K ⊕ W \mathcal{V}=K\oplus W V = K ⊕ W P = ( M , T ) P=(M,T) P = ( M , T ) M M M T T T K K K W W W M M M T T T ( U , T ) (U,T) ( U , T ) M M M k k k M z + u Mz+u M z + u z ∈ F 2 m z\in\mathbb{F}_2^m z ∈ F 2 m u ∈ K u\in K u ∈ K r s r_s r s r s r_s r s
For an independent uniform linear map A : K → F 2 r s A:K\to\mathbb{F}_2^{r_s} A : K → F 2 r s ( M , T ) (M,T) ( M , T ) ( A , T , A M ) (A,T,AM) ( A , T , A M ) U U U T T T { M ′ : A M ′ = A M } \{M':AM'=AM\} { M ′ : A M ′ = A M } K K K U U U U U U M z + u Mz+u M z + u ( U , A , T , A M ) (U,A,T,AM) ( U , A , T , A M ) U U U
The advice experiment compares the equation tuple U U U O O O β \beta β π \pi π ( M O , T O ) (M_O,T_O) ( M O , T O ) O O O A A A ( A , T O ∘ π , A M O ∘ π ) (A,T_O\circ\pi,AM_O\circ\pi) ( A , T O ∘ π , A M O ∘ π ) U U U ( A , T O , A M O ) (A,T_O,AM_O) ( A , T O , A M O ) O O O β \beta β U U U O O O
The two strategies are defined from their respective visible data. When its advice admits a certificate, the U U U O O O { M ′ : A M ′ = A M O } \{M':AM'=AM_O\} { M ′ : A M ′ = A M O } U U U U U U γ > 0 \gamma>0 γ > 0 k k k [28 ] ; the correlated advice and use of vanishing coordinates follow Khot, Minzer, and Safra [26 ] , Sections 3.3–3.4, with later use of that framework by Minzer and Zheng [31 ] , Section 3.
On a NO parity instance, every pair of advice strategies has agreement tending to zero. The choice β = k − 2 / 3 \beta=k^{-2/3} β = k − 2/3 k β 2 → 0 k\beta^2\to0 k β 2 → 0 k β → ∞ k\beta\to\infty k β → ∞ A A A O O O exp ( − c k 1 / 3 ) \exp(-ck^{1/3}) exp ( − c k 1/3 ) k k k
For repetition we use the explicit projection-game bound of Dinur and Steurer [13 ] , Corollary 1.2. Raz established exponential decay for general two-prover games [39 ] , and Holenstein simplified the proof [20 ] ; those bounds depend on the answer alphabet. Rao removed that dependence for projection games [38 ] , Theorem 4. The Dinur–Steurer bound is applied first on the clean coordinates above and finally after rounding the matrix-game weights and subdividing every edge into four edges. Its alphabet independence permits the final repetition exponent to be fixed before the latent alphabet, completing the explicit unweighted reduction.
Figure 1 displays the reduction and the two incompatible bounds that establish soundness.
Figure 1. The solid arrows describe the reduction; the dashed arrows describe its soundness argument. The decoding lower bound follows from high test acceptance, while the clean-coordinate upper bound follows from the NO parity gap and applies to every advice strategy. The constants c c c γ > 0 \gamma> 0 γ > 0 k k k
Section 2 fixes the game and probability conventions. Section 3 constructs the gadget, and Section 4 defines the permutation test. Sections 5 and 6 give the two incompatible bounds on the advice experiment. Section 7 completes the parameter choices and the explicit Unique Games reduction. Section 8 then derives the approximation consequences from the completed theorem and the cited reductions. Appendix A gives the simple strong-left formulation and the finite ordering reduction used there.
Conventions
Weighted games. Intermediate instances may have loops, repeated constraint occurrences, and positive rational weights summing to one. Their value is the maximum total weight satisfied by a labeling. Occurrences retain separate IDs even if their constraints coincide. All rational numbers are encoded by binary numerators and denominators.
A bipartite projection game has a question for each vertex on either side, finite answer sets, and a map from left answers to right answers on each constraint. A strategy chooses one answer to each question. Answer sets that depend on the question can be identified with fixed alphabets of the same size; we use this for the four satisfying triples of a parity equation. Each prover uses only its own question. Private or shared randomness independent of the questions gives a mixture of deterministic strategies and cannot increase value.
The parallel power G ⊗ t G^{\otimes t} G ⊗ t t t t
Binary linear algebra and Fourier analysis. Except where a larger field is specified, all vector spaces and maps are finite-dimensional over F 2 \mathbb{F}_2 F 2 Hom ( E , F ) \operatorname{Hom}(E,F) Hom ( E , F ) E ∗ = Hom ( E , F 2 ) E^*=\operatorname{Hom}(E,\mathbb{F}_2) E ∗ = Hom ( E , F 2 ) S ≤ E ∗ S\le E^* S ≤ E ∗ S ∣ K ≤ K ∗ S|_K\le K^* S ∣ K ≤ K ∗ K ≤ E K\le E K ≤ E dim ( S ∣ K ) \dim(S|_K) dim ( S ∣ K )
For a real function f f f E E E
f ^ ( g ) = E x ∈ E f ( x ) ( − 1 ) g ( x ) , f ( x ) = ∑ g ∈ E ∗ f ^ ( g ) ( − 1 ) g ( x ) , ∑ g ∣ f ^ ( g ) ∣ 2 = E x ∣ f ( x ) ∣ 2 \widehat{f}(g)=\mathbb{E}_{x\in E}f(x)(-1)^{g(x)},\qquad f(x)=\sum_{g\in E^*}\widehat{f}(g)(-1)^{g(x)},\qquad\sum_g|\widehat{f}(g)|^2=\mathbb{E}_{x}|f(x)|^2 f ( g ) = E x ∈ E f ( x ) ( − 1 ) g ( x ) , f ( x ) = g ∈ E ∗ ∑ f ( g ) ( − 1 ) g ( x ) , g ∑ ∣ f ( g ) ∣ 2 = E x ∣ f ( x ) ∣ 2 These identities follow because a nonzero linear functional has equally many zero and one values, so its character has mean zero. The characters are therefore an orthonormal basis. On a space of matrices, this is the entrywise pairing with its dual matrix space; we specify tensor notation when defining the Fourier decoder.
Probability and finite constructions. Uniform sampling from a vector space includes zero. Samples are independent unless a dependence is stated. For finite probability laws,
TV ( P , Q ) = 1 2 ∑ x ∣ P ( x ) − Q ( x ) ∣ . \operatorname{TV}(P,Q)=\frac{1}{2}\sum_x|P(x)-Q(x)|. TV ( P , Q ) = 2 1 x ∑ ∣ P ( x ) − Q ( x ) ∣. It bounds the difference of expectations of any [ 0 , 1 ] [0,1] [ 0 , 1 ]
Random experiments describe finite weighted constraint lists. The reduction enumerates those lists deterministically. Every auxiliary dimension and tuple length is fixed before the input formula varies; the final proof checks both this parameter order and the binary encoding cost. Fourier witnesses and decoders are used only to bound game value and need not be efficient.
A latent alphabet gadget
The construction in this section separates a nonlinear observable from families of linear observables under the same additive noise. All vector spaces and duals in this section are over F 2 \mathbb{F}_2 F 2
Lemma 3.1 (Latent alphabet gadget). For every p ∗ > 0 p_*>0 p ∗ > 0 r ∗ r_* r ∗ ℓ \ell ℓ V V V K = F 2 ℓ K=\mathbb{F}_2^\ell K = F 2 ℓ C : V → K C:V\to K C : V → K μ \mu μ V V V
C ( x + k ) = C ( x ) + k ( x ∈ V , k ∈ K ) , (1) C(x+k)=C(x)+k \qquad(x\in V,\ k\in K), \tag*{(1)} C ( x + k ) = C ( x ) + k ( x ∈ V , k ∈ K ) , (1) and, for independent uniform x ∈ V x\in V x ∈ V a ∼ μ a\sim\mu a ∼ μ
Pr [ C ( x + a ) ≠ C ( x ) ] ≤ p ∗ . \Pr[C(x+a)\ne C(x)]\le p_*. Pr [ C ( x + a ) = C ( x )] ≤ p ∗ . Moreover, every linear subspace G ≤ V ∗ G \leq V^* G ≤ V ∗ dim ( G ∣ K ) ≥ r ∗ \dim(G|_K) \geq r_* dim ( G ∣ K ) ≥ r ∗
Pr a ∼ μ [ there exists g ∈ G with g ( a ) ≠ 0 ] ≥ 1 8 . (2) \Pr_{a\sim\mu}\left[\text{there exists }g \in G\text{ with }g(a) \ne0\right] \geq\frac{1}{8}. \tag*{(2)} a ∼ μ Pr [ there exists g ∈ G with g ( a ) = 0 ] ≥ 8 1 . (2) In particular, r ∗ r_* r ∗ ℓ \ell ℓ p ∗ p_* p ∗
We first construct a gadget with a fixed smaller output space B B B B B B B ∗ B^* B ∗ B → K B \to K B → K K K K B ∗ B^* B ∗ K K K
The fixed-B B B θ \theta θ r r r 3 r θ 3r\theta 3 r θ 3 θ 3\theta 3 θ
The quadratic block
Fix an integer r 0 ≥ 1 r_0 \geq1 r 0 ≥ 1 p ∗ p_* p ∗ H 0 = 0 H_0 = 0 H 0 = 0 H r = ∑ j = 1 r 1 / j H_r = \sum_{j=1}^r 1/j H r = ∑ j = 1 r 1/ j F = F 2 d F = \mathbb{F}_2^d F = F 2 d q = 2 d q = 2^d q = 2 d X = B = F 3 X = B = F^3 X = B = F 3 b = 3 d b = 3d b = 3 d d d d r 0 r_0 r 0
Use the trace pairing to identify both X ∗ X^* X ∗ B ∗ B^* B ∗ F 3 F^3 F 3 z ∈ F 3 z \in F^3 z ∈ F 3 y ↦ Tr F / F 2 ( z ⋅ y ) y \mapsto\operatorname{Tr}_{F/\mathbb{F}_2}(z \cdot y) y ↦ Tr F / F 2 ( z ⋅ y ) Tr \operatorname{Tr} Tr Tr ( t 2 ) = Tr ( t ) \operatorname{Tr}(t^2) = \operatorname{Tr}(t) Tr ( t 2 ) = Tr ( t ) F F F
Define
Q ( x 1 , x 2 , x 3 ) = ( x 2 x 3 , x 1 x 3 , x 1 x 2 ) , D ( x , a ) = Q ( x + a ) + Q ( x ) + Q ( a ) . Q(x_1,x_2,x_3) = (x_2x_3,x_1x_3,x_1x_2), \qquad D(x,a) = Q(x+a) + Q(x) + Q(a). Q ( x 1 , x 2 , x 3 ) = ( x 2 x 3 , x 1 x 3 , x 1 x 2 ) , D ( x , a ) = Q ( x + a ) + Q ( x ) + Q ( a ) . The block observable is
C b l k : X ⊕ B ⟶ B , C b l k ( x , y ) = y + Q ( x ) . C_{\mathrm{blk}} : X \oplus B \longrightarrow B, \qquad C_{\mathrm{blk}}(x,y) = y + Q(x). C blk : X ⊕ B ⟶ B , C blk ( x , y ) = y + Q ( x ) . It is equivariant under the vertical copy of B B B C b l k ( x , y + k ) = C b l k ( x , y ) + k C_{\mathrm{blk}}(x,y+k) = C_{\mathrm{blk}}(x,y) + k C blk ( x , y + k ) = C blk ( x , y ) + k z ∈ B ∗ z \in B^* z ∈ B ∗ z ∘ C b l k z \circ C_{\mathrm{blk}} z ∘ C blk z ( k ) z(k) z ( k ) B B B z z z
For a one-dimensional F F F A = F v A = Fv A = F v F 3 F^3 F 3
D A = { y ∈ B : v ⋅ y = 0 } , U A = { ( a , Q ( a ) + w ) : a ∈ A , w ∈ D A } ⊂ X ⊕ B . (3) D_A = \{y \in B : v \cdot y = 0\}, \qquad U_A = \{(a,Q(a)+w) : a \in A,\ w \in D_A\} \subset X \oplus B. \tag*{(3)} D A = { y ∈ B : v ⋅ y = 0 } , U A = {( a , Q ( a ) + w ) : a ∈ A , w ∈ D A } ⊂ X ⊕ B . (3) These definitions are independent of the chosen nonzero generator v v v q 2 + q + 1 q^2+q+1 q 2 + q + 1
θ = 1 q 2 + q + 1 . \theta= \frac{1}{q^2+q+1}. θ = q 2 + q + 1 1 . Lemma 3.2. For every line A A A U A U_A U A b b b a ∈ A a \in A a ∈ A x ∈ X x \in X x ∈ X D ( x , a ) ∈ D A D(x,a) \in D_A D ( x , a ) ∈ D A a , a ′ ∈ A a,a' \in A a , a ′ ∈ A D ( a , a ′ ) = 0 D(a,a')=0 D ( a , a ′ ) = 0 D A D_A D A B ∗ = F 3 B^*=\mathbb{F}^3 B ∗ = F 3 A A A U A U_A U A X ⊕ B X \oplus B X ⊕ B
Proof. The three coordinates of D ( x , a ) D(x,a) D ( x , a )
x 2 a 3 + a 2 x 3 , x 1 a 3 + a 1 x 3 , x 1 a 2 + a 1 x 2 . x_2a_3+a_2x_3,\qquad x_1a_3+a_1x_3,\qquad x_1a_2+a_1x_2. x 2 a 3 + a 2 x 3 , x 1 a 3 + a 1 x 3 , x 1 a 2 + a 1 x 2 . When a = t v a=tv a = t v v ⋅ D ( x , a ) v\cdot D(x,a) v ⋅ D ( x , a ) v v v Q ∣ A Q|_A Q ∣ A U A U_A U A A ⊕ D A A\oplus D_A A ⊕ D A d + 2 d = b d+2d=b d + 2 d = b
Every z ∈ A z\in A z ∈ A D A D_A D A 3 d − 2 d = d 3d-2d=d 3 d − 2 d = d A A A A = F e i A=F e_i A = F e i U A U_A U A ( F e i , 0 ) (F e_i,0) ( F e i , 0 ) Q ( t e i ) = 0 Q(t e_i)=0 Q ( t e i ) = 0 { 0 } ⊕ D A \{0\}\oplus D_A { 0 } ⊕ D A X ⊕ B X\oplus B X ⊕ B
The nonlinear response. The form of U A U_A U A ( a , Q ( a ) + w ) ∈ U A (a,Q(a)+w)\in U_A ( a , Q ( a ) + w ) ∈ U A
C b l k ( ( x , y ) + ( a , Q ( a ) + w ) ) + C b l k ( x , y ) = w + D ( x , a ) . C_{\mathrm{blk}}((x,y)+(a,Q(a)+w))+C_{\mathrm{blk}}(x,y)=w+D(x,a). C blk (( x , y ) + ( a , Q ( a ) + w )) + C blk ( x , y ) = w + D ( x , a ) . The right-hand side lies in D A D_A D A
Lemma 3.3 (Response to one block update). Fix a line A A A ( x , y ) ∈ X ⊕ B (x,y)\in X\oplus B ( x , y ) ∈ X ⊕ B ζ ∈ U A ∖ { 0 } \zeta\in U_A\setminus\{0\} ζ ∈ U A ∖ { 0 }
Pr [ C b l k ( ( x , y ) + ζ ) ≠ C b l k ( x , y ) ] = 1 − θ . \Pr\left[C_{\mathrm{blk}}((x,y)+\zeta)\ne C_{\mathrm{blk}}(x,y)\right]=1-\theta. Pr [ C blk (( x , y ) + ζ ) = C blk ( x , y ) ] = 1 − θ . Proof. First take ζ \zeta ζ U A U_A U A ( a , Q ( a ) + w ) (a,Q(a)+w) ( a , Q ( a ) + w ) a ∈ A a\in A a ∈ A w ∈ D A w\in D_A w ∈ D A x , a x,a x , a w + D ( x , a ) w+D(x,a) w + D ( x , a ) D A D_A D A 1 − q − 2 1-q^{-2} 1 − q − 2 q − 3 q^{-3} q − 3
1 − q − 2 1 − q − 3 = q ( q + 1 ) q 2 + q + 1 = 1 − θ . \frac{1-q^{-2}}{1-q^{-3}}=\frac{q(q+1)}{q^2+q+1}=1-\theta. 1 − q − 3 1 − q − 2 = q 2 + q + 1 q ( q + 1 ) = 1 − θ . The lemma concerns an independent uniform aggregate and uniform nonzero update. When the update comes from a lower level of the recursion, we will verify this conditional law before applying the lemma.
Linear restrictions. Fix a binary subspace S ≤ B ∗ S\le B^* S ≤ B ∗ X ⊕ B X\oplus B X ⊕ B B B B z ∈ S z\in S z ∈ S ( γ z , z ) ∈ X ∗ ⊕ B ∗ (\gamma_z,z)\in X^*\oplus B^* ( γ z , z ) ∈ X ∗ ⊕ B ∗ z ∈ S z\in S z ∈ S γ : S → X ∗ \gamma:S\to X^* γ : S → X ∗ U A U_A U A
Lemma 3.4 (Kernel of a block restriction). Let S ≤ B ∗ S\le B^* S ≤ B ∗ γ : S → X ∗ \gamma:S\to X^* γ : S → X ∗ A A A
κ A , γ : S ⟶ U A ∗ , κ A , γ ( z ) = ( γ z , z ) ∣ U A . \kappa_{A,\gamma}:S\longrightarrow U_A^*,\qquad\kappa_{A,\gamma}(z)=(\gamma_z,z)|_{U_A}. κ A , γ : S ⟶ U A ∗ , κ A , γ ( z ) = ( γ z , z ) ∣ U A . Under the trace identification, write γ z ( x ) = Tr ( g ( z ) ⋅ x ) \gamma_z(x)=\operatorname{Tr}(g(z)\cdot x) γ z ( x ) = Tr ( g ( z ) ⋅ x ) g : S → F 3 g:S\to F^3 g : S → F 3 z ∈ S z\in S z ∈ S
κ A , γ ( z ) = 0 ⟺ A = F z and z ⋅ g ( z ) = z 1 z 2 z 3 . \kappa_{A,\gamma}(z)=0 \quad\Longleftrightarrow\quad A=Fz \quad\text{and}\quad z\cdot g(z)=\sqrt{z_1z_2z_3}. κ A , γ ( z ) = 0 ⟺ A = F z and z ⋅ g ( z ) = z 1 z 2 z 3 . Proof. If z z z ( 0 , w ) (0,w) ( 0 , w ) w ∈ D A w\in D_A w ∈ D A z ∈ A z\in A z ∈ A z ≠ 0 z\ne0 z = 0 A = F z A=Fz A = F z ( t z , Q ( t z ) ) (tz,Q(tz)) ( t z , Q ( t z )) t ∈ F t\in F t ∈ F
Tr ( t g ( z ) ⋅ z + t 2 z 1 z 2 z 3 ) (4) \operatorname{Tr}\left(t\,g(z)\cdot z+t^2z_1z_2z_3\right) \tag*{(4)} Tr ( t g ( z ) ⋅ z + t 2 z 1 z 2 z 3 ) (4) The three summands of z ⋅ Q ( t z ) z\cdot Q(tz) z ⋅ Q ( t z )
Tr ( t 2 c ) = Tr ( t c ) . \operatorname{Tr}(t^2c)=\operatorname{Tr}(t\sqrt{c}). Tr ( t 2 c ) = Tr ( t c ) . Nondegeneracy of the trace pairing shows that Equation (4) vanishes for every t t t z ⋅ g ( z ) = z 1 z 2 z 3 z\cdot g(z)=\sqrt{z_1z_2z_3} z ⋅ g ( z ) = z 1 z 2 z 3 z ∈ A z\in A z ∈ A □ \square □
Generic spaces of characters
The kernel criterion suggests two sufficient controls. We shall use a family in which no field line contains two nonzero characters and only a few characters satisfy the alignment equation for any one choice of extensions. The uniformity over that choice will later allow a lift to depend on earlier random changes of coordinates.
Definition 3.5. A binary subspace S ≤ F 3 S\le F^3 S ≤ F 3 r ≥ 1 r\ge1 r ≥ 1 generic if no two distinct nonzero elements of S S S F F F g : S → F 3 g:S\to F^3 g : S → F 3 3 r 3r 3 r z ∈ S z\in S z ∈ S
z ⋅ g ( z ) = z 1 z 2 z 3 . z\cdot g(z)=\sqrt{z_1z_2z_3}. z ⋅ g ( z ) = z 1 z 2 z 3 . Fix one map γ : S → X ∗ \gamma:S\to X^* γ : S → X ∗ A A A r A = dim im κ A , γ r_A=\dim\operatorname{im}\kappa_{A,\gamma} r A = dim im κ A , γ r = dim S > 0 r=\dim S>0 r = dim S > 0 S S S S S S g g g γ \gamma γ 3 r 3r 3 r (3.8) ; hence at most 3 r 3r 3 r
r − r A ≤ 1 , Pr A [ r A < r ] ≤ 3 r θ , E A [ H r − H r A ] ≤ 3 θ . (5) r-r_A\le1,\qquad\Pr_A[r_A<r]\le3r\theta,\qquad\mathbb{E}_A[H_r-H_{r_A}]\le3\theta. \tag*{(5)} r − r A ≤ 1 , A Pr [ r A < r ] ≤ 3 r θ , E A [ H r − H r A ] ≤ 3 θ . (5) The last bound uses H r − H r − 1 = 1 / r H_r-H_{r-1}=1/r H r − H r − 1 = 1/ r r r r A = F z A=Fz A = F z z ∈ S z\in S z ∈ S
Pr A [ r A < r ] ≤ ( 2 r − 1 ) θ ≤ 2 r θ , H r − H r A ≤ H r . \Pr_A[r_A<r]\le(2^r-1)\theta\le2^r\theta,\qquad H_r-H_{r_A}\le H_r. A Pr [ r A < r ] ≤ ( 2 r − 1 ) θ ≤ 2 r θ , H r − H r A ≤ H r . These estimates concern rank under restriction. Detection of the eventual noise will follow only after a positive-rank family reaches a leaf.
It remains to show that spaces with the stated genericity are abundant.
Lemma 3.6. For each fixed r ≥ 1 r\ge1 r ≥ 1 r r r F 3 F^3 F 3 d → ∞ d\to\infty d → ∞ Proof. Choose independent uniform x i j ∈ F x_{ij} \in F x ij ∈ F 1 ≤ i ≤ 3 1 \le i \le3 1 ≤ i ≤ 3 1 ≤ j ≤ r 1 \le j \le r 1 ≤ j ≤ r
z i ( t ) = ∑ j = 1 r x i j t j , t ∈ F 2 r . z_i(t) = \sum_{j=1}^{r} x_{ij}t_j,\qquad t \in\mathbb{F}_2^r. z i ( t ) = j = 1 ∑ r x ij t j , t ∈ F 2 r . Each nonzero input has uniform image in F 3 F^3 F 3 ( 2 r − 1 ) q − 3 (2^r-1)q^{-3} ( 2 r − 1 ) q − 3 r r r F F F F 3 F^3 F 3 O r ( q − 2 ) O_r(q^{-2}) O r ( q − 2 )
It remains to prove the alignment condition simultaneously for all g g g E E E 3 r 3r 3 r F 2 r \mathbb{F}_2^r F 2 r g g g F 3 F^3 F 3 E E E
c = ( z 1 ( t ) z 2 ( t ) z 3 ( t ) ) t ∈ E c=\left(\sqrt{z_1(t)z_2(t)z_3(t)}\right)_{t\in E} c = ( z 1 ( t ) z 2 ( t ) z 3 ( t ) ) t ∈ E lies in the F F F 3 r 3r 3 r
M t , ( i , j ) = t j z i ( t ) , t ∈ E , 1 ≤ i ≤ 3 , 1 ≤ j ≤ r . M_{t,(i,j)}=t_jz_i(t),\qquad t\in E,\quad1\le i\le3,\quad1\le j\le r. M t , ( i , j ) = t j z i ( t ) , t ∈ E , 1 ≤ i ≤ 3 , 1 ≤ j ≤ r . Conversely, membership supplies the basis values of such a g g g g g g
First regard the x i j x_{ij} x ij L = F 2 ( x i j ) L=F_2(x_{ij}) L = F 2 ( x ij ) c c c M M M L ‾ \overline{L} L r 3 r^3 r 3 L ‾ \overline{L} L
x 1 j x 2 k x 3 l , 1 ≤ j , k , l ≤ r . \sqrt{x_{1j}x_{2k}x_{3l}},\qquad1\le j,k,l\le r. x 1 j x 2 k x 3 l , 1 ≤ j , k , l ≤ r . Indeed, after clearing denominators, a dependence would be a polynomial identity in the square roots of the indeterminates. The displayed monomials have distinct parity vectors, whereas coefficients polynomial in the x i j x_{ij} x ij
The expansion of c c c
v j k l = ( t j t k t l ) t ∈ E . v_{jkl}=(t_jt_kt_l)_{t\in E}. v j k l = ( t j t k t l ) t ∈ E . Suppose that c c c L ‾ \overline{L} L L ‾ \overline{L} L M M M c c c v j k l v_{jkl} v j k l L E L^E L E v j k l v_{jkl} v j k l L L L
For h ≥ 1 h\ge1 h ≥ 1 V h ≤ L E V_h\le L^E V h ≤ L E t 1 , … , t r t_1,\ldots,t_r t 1 , … , t r h h h v j k l v_{jkl} v j k l t i 2 = t i t_i^2=t_i t i 2 = t i
V 3 ⊆ col L ( M ) ⊆ V 2 ⊆ V 3 . V_3\subseteq\operatorname{col}_L(M)\subseteq V_2\subseteq V_3. V 3 ⊆ col L ( M ) ⊆ V 2 ⊆ V 3 . These three spaces are equal. Multiplication by any t i t_i t i V 2 V_2 V 2 V 3 V_3 V 3 L E L^E L E t i t_i t i 1 + t i 1+t_i 1 + t i t i t_i t i E E E ∣ E ∣ > 3 r |E|>3r ∣ E ∣ > 3 r
To pass from this algebraic statement to finite fields, square the entries of both M M M c c c z 1 ( t ) z 2 ( t ) z 3 ( t ) z_1(t)z_2(t)z_3(t) z 1 ( t ) z 2 ( t ) z 3 ( t ) h = rank L M ≤ 3 r h=\operatorname{rank}_{L} M\le3r h = rank L M ≤ 3 r L ‾ \overline{L} L h + 1 h+1 h + 1 2 h + 3 ≤ 6 r + 3 2h+3\le6r+3 2 h + 3 ≤ 6 r + 3 h + 1 h+1 h + 1 x i j ∈ F x_{ij}\in F x ij ∈ F ( 6 r + 3 ) / q (6r+3)/q ( 6 r + 3 ) / q [40 ] ; see also the earlier sparse-polynomial formulation in [42 ] .
If the alignment condition fails, it fails on some set E E E 3 r + 1 3r+1 3 r + 1 r r r 2 r − 1 ≤ 3 r 2^r-1\le3r 2 r − 1 ≤ 3 r
Genericity therefore controls every possible map g g g r 0 r_0 r 0 ε 0 \varepsilon_0 ε 0
H r 0 2 r 0 ε 0 ≤ 1 , ε 0 < 1. (6) H_{r_0}2^{r_0}\varepsilon_0\le1,\qquad\varepsilon_0<1. \tag*{(6)} H r 0 2 r 0 ε 0 ≤ 1 , ε 0 < 1. (6) By Lemma 3.6, we may fix d d d b = 3 d ≥ r 0 b=3d\ge r_0 b = 3 d ≥ r 0 1 ≤ r ≤ r 0 1\le r\le r_0 1 ≤ r ≤ r 0 r r r B ∗ B^* B ∗ ε 0 \varepsilon_0 ε 0 r 0 r_0 r 0
Concatenation and its noise
We keep the output space B B B
We construct binary input spaces P t P_t P t R t ≤ P t R_t\le P_t R t ≤ P t λ t : R t → B \lambda_t:R_t\to B λ t : R t → B C t : P t → B C_t:P_t\to B C t : P t → B
C t ( u + h ) = C t ( u ) + λ t ( h ) ( h ∈ R t ) . C_t(u+h)=C_t(u)+\lambda_t(h)\qquad(h\in R_t). C t ( u + h ) = C t ( u ) + λ t ( h ) ( h ∈ R t ) . A shift h ∈ R t h\in R_t h ∈ R t λ t ( h ) \lambda_t(h) λ t ( h )
At height zero take P 0 = R 0 = B P_0=R_0=B P 0 = R 0 = B C 0 = λ 0 = id B C_0=\lambda_0=\operatorname{id}_B C 0 = λ 0 = id B I \mathcal{I} I ( A , J ) (A,J) ( A , J ) A A A F 3 F^3 F 3 J : B → U A J:B\to U_A J : B → U A
We include one child for every ( A , J ) (A,J) ( A , J ) t ≥ 1 t\ge1 t ≥ 1 P t = ∏ ( A , J ) ∈ I P t − 1 P_t=\prod_{(A,J)\in\mathcal{I}}P_{t-1} P t = ∏ ( A , J ) ∈ I P t − 1
( x , y ) = ∑ A , J J C t − 1 ( u A J ) , C t ( u ) = C b l k ( x , y ) = y + Q ( x ) . (x,y)=\sum_{A,J}J C_{t-1}(u_{AJ}),\qquad C_t(u)=C_{\mathrm{blk}}(x,y)=y+Q(x). ( x , y ) = A , J ∑ J C t − 1 ( u A J ) , C t ( u ) = C blk ( x , y ) = y + Q ( x ) . A tuple of child shifts changes this aggregate by the sum of their embedded output translations. To make the parent change a pure output translation, we require the X X X
R t = { ( h A J ) ∈ ∏ A , J R t − 1 : ∑ A , J J λ t − 1 ( h A J ) ∈ { 0 } ⊕ B } , R_t=\left\{(h_{AJ})\in\prod_{A,J}R_{t-1}:\sum_{A,J}J\lambda_{t-1}(h_{AJ})\in\{0\}\oplus B\right\}, R t = ⎩ ⎨ ⎧ ( h A J ) ∈ A , J ∏ R t − 1 : A , J ∑ J λ t − 1 ( h A J ) ∈ { 0 } ⊕ B ⎭ ⎬ ⎫ , and let λ t ( h ) = k \lambda_t(h)=k λ t ( h ) = k ( 0 , k ) (0,k) ( 0 , k ) (3.12) follows immediately from Equation (3.13) . Surjectivity follows inductively from Lemma 3.2: the child output translations can be chosen arbitrarily, and their aggregate map is onto X ⊕ B X\oplus B X ⊕ B (3.12) and surjectivity also show that C t C_t C t B B B
Let ξ t \xi_t ξ t P t P_t P t B B B ( A , J ) (A,J) ( A , J ) ξ t − 1 \xi_{t-1} ξ t − 1 B B B A A A J J J Figure 2 illustrates one level of the recursion and the selected noisy branch.
Figure 2. One level of the latent recursion, shown under its additive noise. The input space is a product over all child indices ( A , J ) (A,J) ( A , J ) U A ≤ X ⊕ B U_A\leq X\oplus B U A ≤ X ⊕ B ( x , y ) (x,y) ( x , y ) Δ \Delta Δ ( x ′ , y ′ ) = ( x , y ) + J ∗ Δ (x',y')=(x,y)+J_*\Delta ( x ′ , y ′ ) = ( x , y ) + J ∗ Δ
Lemma 3.7. For independent uniform u ∈ P t u\in P_t u ∈ P t ξ t \xi_t ξ t
p t : = Pr [ C t ( u + ξ t ) ≠ C t ( u ) ] = ( 1 − q − 3 ) ( 1 − θ ) t . p_t:=\Pr[C_t(u+\xi_t)\ne C_t(u)]=(1-q^{-3})(1-\theta)^t. p t := Pr [ C t ( u + ξ t ) = C t ( u )] = ( 1 − q − 3 ) ( 1 − θ ) t . Proof. The identity at height zero is immediate. Consider one higher level and condition on the selected child ( A , J ) (A,J) ( A , J ) Δ \Delta Δ Δ \Delta Δ
We need also the conditional law of the child’s initial output. For any fixed child perturbation a a a (3.12) gives
C t − 1 ( u + a + h ) + C t − 1 ( u + h ) = C t − 1 ( u + a ) + C t − 1 ( u ) ( h ∈ R t − 1 ) . C_{t-1}(u+a+h)+C_{t-1}(u+h)=C_{t-1}(u+a)+C_{t-1}(u)\qquad(h\in R_{t-1}). C t − 1 ( u + a + h ) + C t − 1 ( u + h ) = C t − 1 ( u + a ) + C t − 1 ( u ) ( h ∈ R t − 1 ) . Thus the difference is invariant under these shifts, while the initial output is translated by every element of B B B X ⊕ B X \oplus B X ⊕ B ( x , y ) (x,y) ( x , y ) ( A , J , Δ ) (A,J,\Delta) ( A , J , Δ ) J Δ J\Delta J Δ
Conditional on Δ ≠ 0 \Delta\ne0 Δ = 0 A A A J J J Δ \Delta Δ J Δ J\Delta J Δ U A ∖ { 0 } U_A \setminus\{0\} U A ∖ { 0 } 1 − θ 1-\theta 1 − θ Δ = 0 \Delta=0 Δ = 0 p t = p t − 1 ( 1 − θ ) p_t=p_{t-1}(1-\theta) p t = p t − 1 ( 1 − θ )
Linear lifts and loss of rank
The nonlinear change probability now decays with the height. For the fixed-B B B B ∗ B^* B ∗
For S ≤ B ∗ S \le B^* S ≤ B ∗ P t P_t P t z ↦ ψ z z \mapsto\psi_z z ↦ ψ z S S S P t ∗ P_t^* P t ∗
ψ z ∣ R t = z ∘ λ t . \psi_z|_{R_t}=z\circ\lambda_t. ψ z ∣ R t = z ∘ λ t . A lift is full when its domain is B ∗ B^* B ∗
Lemma 3.8. Let a lift with domain S S S P t P_t P t t ≥ 1 t \ge1 t ≥ 1 ( A , J ) (A,J) ( A , J ) λ t − 1 \lambda_{t-1} λ t − 1 B B B
ϕ A J ( z ) = J ∗ ( ( γ z , z ) ∣ U A ) ∈ B ∗ , \phi_{AJ}(z)=J^*((\gamma_z,z)|_{U_A})\in B^*, ϕ A J ( z ) = J ∗ (( γ z , z ) ∣ U A ) ∈ B ∗ , where γ : S → X ∗ \gamma:S\to X^* γ : S → X ∗
Proof. A shift supported on one child and lying in ker λ t − 1 \ker\lambda_{t-1} ker λ t − 1 ψ z \psi_z ψ z
Let T = ∏ A , J B T=\prod_{A,J}B T = ∏ A , J B A : T → X ⊕ B \mathcal{A}:T\to X\oplus B A : T → X ⊕ B z z z A \mathcal{A} A A \mathcal{A} A A \mathcal{A} A X X X γ z \gamma_z γ z γ z \gamma_z γ z z z z (3.17) .
After choosing a child, let S ′ = im ϕ A J S'=\operatorname{im}\phi_{AJ} S ′ = im ϕ A J ι : S ′ → S \iota:S'\to S ι : S ′ → S ϕ A J \phi_{AJ} ϕ A J ψ ι ( z ′ ) \psi_{\iota(z')} ψ ι ( z ′ ) S ′ S' S ′ P t − 1 P_{t-1} P t − 1
The factorization now connects the recursion to the local restriction problem. For a fixed parent lift, its single map γ \gamma γ A A A ϕ A J = J ∗ κ A , γ \phi_{AJ}=J^*\kappa_{A,\gamma} ϕ A J = J ∗ κ A , γ J ∗ J^* J ∗
Proposition 3.9. Set
s = ⌊ H r 0 8 θ ⌋ . s=\left\lfloor\frac{H_{r_0}}{8\theta}\right\rfloor. s = ⌊ 8 θ H r 0 ⌋ . Every full lift on P s P_s P s ξ s \xi_s ξ s 1 / 4 1/4 1/4
Pr [ there exists z ∈ B ∗ with ψ z ( ξ s ) ≠ 0 ] ≥ 1 4 . (7) \Pr[\text{there exists }z\in B^*\text{ with }\psi_z(\xi_s)\ne0]\ge\frac{1}{4}. \tag*{(7)} Pr [ there exists z ∈ B ∗ with ψ z ( ξ s ) = 0 ] ≥ 4 1 . (7) Proof. Restrict the full lift at the top to the fixed generic subspace of dimension r 0 r_0 r 0 S j S_j S j j j j r j = dim S j r_j=\dim S_j r j = dim S j r j = r 0 r_j=r_0 r j = r 0 j = 0 j=0 j = 0
We spell out the conditioning that permits genericity to be used at every level. Let F j \mathcal{F}_j F j ( A j , J j ) (A_j,J_j) ( A j , J j ) j j j γ j \gamma_j γ j F j \mathcal{F}_j F j F j \mathcal{F}_j F j A j A_j A j
E j , A j = im [ z ↦ ( γ j , z , z ) ∣ U A j ] ≤ U A j ∗ E_{j,A_j}=\operatorname{im}\left[z\mapsto(\gamma_{j,z},z)\mathbin{|}_{U_{A_j}}\right]\le U_{A_j}^* E j , A j = im [ z ↦ ( γ j , z , z ) ∣ U A j ] ≤ U A j ∗ is fixed. The next domain and its rank are
S j + 1 = J j ∗ E j , A j , r j + 1 = dim E j , A j . S_{j+1}=J_j^*E_{j,A_j},\qquad r_{j+1}=\dim E_{j,A_j}. S j + 1 = J j ∗ E j , A j , r j + 1 = dim E j , A j . The rank is fixed before J j J_j J j J j : B → U A j J_j:B\to U_{A_j} J j : B → U A j S j + 1 S_{j+1} S j + 1 B ∗ B^* B ∗ B j B_j B j r j > 0 r_j>0 r j > 0 S j S_j S j
E [ B j + 1 ∣ F j , A j ] ≤ ε 0 . (8) \mathbb{E}[B_{j+1}\mid\mathcal{F}_j,A_j]\le\varepsilon_0. \tag*{(8)} E [ B j + 1 ∣ F j , A j ] ≤ ε 0 . (8) The next lift may depend on J j J_j J j g g g
Let Δ j = H r j − H r j + 1 ≥ 0 \Delta_j=H_{r_j}-H_{r_{j+1}}\ge0 Δ j = H r j − H r j + 1 ≥ 0 F j \mathcal{F}_j F j A j A_j A j
E [ Δ j ∣ F j ] ≤ 3 θ + H r 0 2 r 0 θ B j . (9) \mathbb{E}[\Delta_j\mid\mathcal{F}_j]\le3\theta+H_{r_0}2^{r_0}\theta B_j. \tag*{(9)} E [ Δ j ∣ F j ] ≤ 3 θ + H r 0 2 r 0 θ B j . (9) For j = 0 j=0 j = 0 3 θ 3\theta 3 θ j ≥ 1 j\ge1 j ≥ 1 (9) over the preceding isomorphism using Equation (8) . This gives the unconditional bound
E Δ j ≤ ( 3 + H r 0 2 r 0 ε 0 ) θ ≤ 4 θ . \mathbb{E}\Delta_j\le(3+H_{r_0}2^{r_0}\varepsilon_0)\theta\le4\theta. E Δ j ≤ ( 3 + H r 0 2 r 0 ε 0 ) θ ≤ 4 θ . No independence between an incoming orientation and its subsequent lift has been assumed.
Summing the expected drops and using Equation (3.18) ,
E [ H r 0 − H r s ] ≤ 4 s θ ≤ H r 0 2 . \mathbb{E}[H_{r_0}-H_{r_s}]\le4s\theta\le\frac{H_{r_0}}{2}. E [ H r 0 − H r s ] ≤ 4 s θ ≤ 2 H r 0 . Extinction requires a total drop of H r 0 H_{r_0} H r 0 Pr [ r s = 0 ] ≤ 1 / 2 \Pr[r_s=0]\le1/2 Pr [ r s = 0 ] ≤ 1/2 P 0 = R 0 = B P_0=R_0=B P 0 = R 0 = B r s > 0 r_s>0 r s > 0 B B B 1 − 2 − r s ≥ 1 / 2 1-2^{-r_s}\ge1/2 1 − 2 − r s ≥ 1/2 ξ s \xi_s ξ s (7) .
Quotients and enlargement
The fixed-B B B
V 0 = P s / ker λ s , V_0 = P_s / \ker\lambda_s, V 0 = P s / ker λ s , where the kernel is taken inside R s ≤ P s R_s \leq P_s R s ≤ P s q 0 : P s → V 0 q_0 : P_s \to V_0 q 0 : P s → V 0 (3.12) makes C s C_s C s C ‾ : V 0 → B \overline{C} : V_0 \to B C : V 0 → B R s / ker λ s R_s / \ker\lambda_s R s / ker λ s B B B λ s \lambda_s λ s i B : B → V 0 i_B : B \to V_0 i B : B → V 0
q 0 ( h ) = i B ( λ s h ) ( h ∈ R s ) . q_0(h) = i_B(\lambda_s h) \qquad(h \in R_s). q 0 ( h ) = i B ( λ s h ) ( h ∈ R s ) . We henceforth identify this subspace with B B B
C ‾ ( x + b ′ ) = C ‾ ( x ) + b ′ ( b ′ ∈ B ) . \overline{C}(x+b') = \overline{C}(x)+b' \qquad(b' \in B). C ( x + b ′ ) = C ( x ) + b ′ ( b ′ ∈ B ) . Let ν \nu ν ξ s \xi_s ξ s P s P_s P s V 0 V_0 V 0 p s p_s p s
Every linear subspace G 0 ≤ V 0 ∗ G_0 \leq V_0^* G 0 ≤ V 0 ∗ B ∗ B^* B ∗
Pr a ∼ ν [ there exists g ∈ G 0 with g ( a ) ≠ 0 ] ≥ 1 4 . (10) \Pr_{a \sim\nu}\left[\text{there exists }g \in G_0\text{ with }g(a) \ne0\right] \geq\frac{1}{4}. \tag*{(10)} a ∼ ν Pr [ there exists g ∈ G 0 with g ( a ) = 0 ] ≥ 4 1 . (10) Indeed, choose a linear section σ : B ∗ → G 0 \sigma: B^* \to G_0 σ : B ∗ → G 0 ψ z = q 0 ∗ σ ( z ) = σ ( z ) ∘ q 0 \psi_z = q_0^*\sigma(z) = \sigma(z) \circ q_0 ψ z = q 0 ∗ σ ( z ) = σ ( z ) ∘ q 0 h ∈ R s h \in R_s h ∈ R s
ψ z ( h ) = σ ( z ) ( q 0 h ) = z ( λ s h ) . \psi_z(h) = \sigma(z)(q_0h) = z(\lambda_s h). ψ z ( h ) = σ ( z ) ( q 0 h ) = z ( λ s h ) . Thus this pullback is a full lift. Moreover, ψ z ( ξ s ) = σ ( z ) ( q 0 ξ s ) \psi_z(\xi_s) = \sigma(z)(q_0\xi_s) ψ z ( ξ s ) = σ ( z ) ( q 0 ξ s ) G 0 G_0 G 0
Proof of Lemma 3.1. Choose r 0 r_0 r 0
exp ( 1 − H r 0 / 8 ) ≤ p ∗ . \exp(1-H_{r_0}/8) \leq p_*. exp ( 1 − H r 0 /8 ) ≤ p ∗ . Then choose ϵ 0 \epsilon_0 ϵ 0 (6) and fix d d d b = 3 d b=3d b = 3 d θ \theta θ s s s (3.18) and the quotient ( V 0 , B , C ‾ , ν ) (V_0,B,\overline{C},\nu) ( V 0 , B , C , ν )
p s ≤ ( 1 − θ ) s ≤ exp ( − θ s ) ≤ exp ( θ − H r 0 / 8 ) ≤ p ∗ . (11) p_s \leq(1-\theta)^s \leq\exp(-\theta s) \leq\exp(\theta-H_{r_0}/8) \leq p_*. \tag*{(11)} p s ≤ ( 1 − θ ) s ≤ exp ( − θ s ) ≤ exp ( θ − H r 0 /8 ) ≤ p ∗ . (11) Set r ∗ = b + 2 r_* = b+2 r ∗ = b + 2 p ∗ p_* p ∗
We now enlarge the output space. The point of using random injections B → K B \to K B → K b + 2 b+2 b + 2 K K K B ∗ B^* B ∗
Fix ℓ ≥ b + 2 \ell\geq b+2 ℓ ≥ b + 2 K = F 2 ℓ K = \mathbb{F}_2^\ell K = F 2 ℓ L \mathcal{L} L L : B → K L:B \to K L : B → K P = ∏ L ∈ L V 0 P = \prod_{L \in\mathcal{L}} V_0 P = ∏ L ∈ L V 0
C ~ ( ( x L ) L ) = ∑ L ∈ L L C ‾ ( x L ) . \widetilde{C}\bigl((x_L)_L\bigr) = \sum_{L \in\mathcal{L}} L\overline{C}(x_L). C ( ( x L ) L ) = L ∈ L ∑ L C ( x L ) . The product of shift subspaces T = ∏ L B ≤ P T = \prod_L B \leq P T = ∏ L B ≤ P
Λ : T ⟶ K , Λ ( ( b L ) L ) = ∑ L L b L . \Lambda:T \longrightarrow K,\qquad\Lambda\bigl((b_L)_L\bigr)=\sum_L Lb_L. Λ : T ⟶ K , Λ ( ( b L ) L ) = L ∑ L b L . This map is onto, because every nonzero vector of K K K B → K B \to K B → K T T T
V = P / ker Λ . \mathcal{V}=P/\ker\Lambda. V = P / ker Λ. The map C ~ \widetilde{C} C C : V → K C:\mathcal{V}\to K C : V → K T / ker Λ T/\ker\Lambda T / ker Λ K K K (1) .
On P P P L ∈ L L\in\mathcal{L} L ∈ L ν \nu ν μ \mu μ L L L p s p_s p s (11) proves Equation (3.2) .
Every noise distribution used here is obtained from uniform finite choices by pushforward, and therefore is rational.
It remains to establish detection for an arbitrary G ≤ V ∗ G\le\mathcal{V}^* G ≤ V ∗ S = G ∣ K ≤ K ∗ S=G|_K\le K^* S = G ∣ K ≤ K ∗ r ≥ r ∗ r\ge r_* r ≥ r ∗ G G G P P P V 0 ∗ V_0^* V 0 ∗ L L L V 0 ∗ V_0^* V 0 ∗ G L G_L G L B B B
G L ∣ B = L ∗ S . G_L|_B=L^*S. G L ∣ B = L ∗ S . To see this, a shift b ′ ∈ B b'\in B b ′ ∈ B L L L L b ′ ∈ K Lb'\in K L b ′ ∈ K z ∈ S z\in S z ∈ S z ( L b ′ ) z(Lb') z ( L b ′ )
The map L ∗ : S → B ∗ L^*:S\to B^* L ∗ : S → B ∗ b ′ ∈ B b'\in B b ′ ∈ B L b ′ ∈ S ⊥ Lb'\in S^\perp L b ′ ∈ S ⊥ b ′ b' b ′ L L L L b ′ Lb' L b ′ K K K
Pr L [ L b ′ ∈ S ⊥ ] = 2 ℓ − r − 1 2 ℓ − 1 ≤ 2 − r . \Pr_L[Lb'\in S^\perp]=\frac{2^{\ell-r}-1}{2^\ell-1}\le2^{-r}. L Pr [ L b ′ ∈ S ⊥ ] = 2 ℓ − 1 2 ℓ − r − 1 ≤ 2 − r . A union bound gives
Pr L [ L ∗ S ≠ B ∗ ] ≤ ( 2 b − 1 ) 2 − r ≤ 2 b − r ≤ 1 4 . \Pr_L[L^*S\ne B^*]\le(2^b-1)2^{-r}\le2^{b-r}\le\frac{1}{4}. L Pr [ L ∗ S = B ∗ ] ≤ ( 2 b − 1 ) 2 − r ≤ 2 b − r ≤ 4 1 . On each of the remaining copies, Equation (10) gives detection probability at least 1 / 4 1/4 1/4 G L G_L G L G G G 3 4 ⋅ 1 4 = 3 16 ≥ 1 8 \frac{3}{4}\cdot\frac{1}{4}=\frac{3}{16}\ge\frac{1}{8} 4 3 ⋅ 4 1 = 16 3 ≥ 8 1 (2) . The construction works for every ℓ ≥ b + 2 \ell\ge b+2 ℓ ≥ b + 2 r ∗ = b + 2 r_*=b+2 r ∗ = b + 2
For completeness, all choices are effective when p ∗ p_* p ∗ m ≥ 0 m\ge0 m ≥ 0 2 − m ≤ p ∗ 2^{-m}\le p_* 2 − m ≤ p ∗ r 0 r_0 r 0 H r 0 ≥ 8 ( m + 1 ) H_{r_0}\ge8(m+1) H r 0 ≥ 8 ( m + 1 ) e − m ≤ 2 − m e^{-m}\le2^{-m} e − m ≤ 2 − m r 0 r_0 r 0 ε 0 \varepsilon_0 ε 0 (6) . For successive integers d d d 3 d ≥ r 0 3d\ge r_0 3 d ≥ r 0 F 2 d \mathbb{F}_2^d F 2 d 1 , … , r 0 1,\ldots,r_0 1 , … , r 0 ε 0 \varepsilon_0 ε 0 r 0 r_0 r 0
The outer questions and the permutation test
We now use the latent gadget to construct a permutation instance. Its vertices encode affine tables on tuples of parity equations. We identify two tables exactly when they induce the same affine map on the same retained coordinates, including the same intercept. This common representation will allow us to compare an equation tuple with a sparsely projected tuple in Section 5.
Weighted parity equations and distinct positions
A weighted parity instance consists of a finite variable set X \mathcal{X} X E \mathcal{E} E w e w_e w e
x v e , 1 + x v e , 2 + x v e , 3 = b e , b e ∈ F 2 . x_{v_{e,1}}+x_{v_{e,2}}+x_{v_{e,3}}=b_e,\qquad b_e\in\mathbb{F}_2. x v e , 1 + x v e , 2 + x v e , 3 = b e , b e ∈ F 2 . Its value is the weighted fraction of equations satisfied, and OPT ( E ) \operatorname{OPT}(\mathcal{E}) OPT ( E )
Theorem 4.1 (Weighted parity gap). For every fixed rational ξ > 0 \xi>0 ξ > 0
YES: OPT ( E ) ≥ 1 − ξ , NO: OPT ( E ) ≤ 1 2 + ξ . \begin{aligned}
\text{YES:}\quad&\operatorname{OPT}(\mathcal{E})\ge1-\xi,\\
\text{NO:}\quad&\operatorname{OPT}(\mathcal{E})\le\frac{1}{2}+\xi.
\end{aligned} YES: NO: OPT ( E ) ≥ 1 − ξ , OPT ( E ) ≤ 2 1 + ξ . The running-time polynomial may depend on ξ \xi ξ
This is the gap consequence of Håstad’s construction in [18 ] , Theorem 5.4 and its proof. More specifically, the proof uses a fixed dyadic verifier error δ > 0 \delta>0 δ > 0 1 − δ 1-\delta 1 − δ ( 1 + δ ) / 2 (1+\delta)/2 ( 1 + δ ) /2 δ ≤ ξ \delta\le\xi δ ≤ ξ
Lemma 4.2 (Making positions distinct). From a weighted parity instance E \mathcal{E} E E ′ \mathcal{E}' E ′
OPT ( E ′ ) ≥ OPT ( E ) , OPT ( E ′ ) ≤ 1 + OPT ( E ) 2 + 3 100 . \operatorname{OPT}(\mathcal{E}')\ge\operatorname{OPT}(\mathcal{E}),\qquad\operatorname{OPT}(\mathcal{E}')\le\frac{1+\operatorname{OPT}(\mathcal{E})}{2}+\frac{3}{100}. OPT ( E ′ ) ≥ OPT ( E ) , OPT ( E ′ ) ≤ 2 1 + OPT ( E ) + 100 3 . In particular, Theorem 4.1 with ξ < 1 / 100 \xi<1/100 ξ < 1/100 1 − ξ 1-\xi 1 − ξ 4 / 5 4/5 4/5
Proof. Replace each variable v v v ( v , c ) (v,c) ( v , c ) c ∈ [ 100 ] c\in[100] c ∈ [ 100 ] 100 3 100^3 10 0 3
For the upper bound fix arbitrary clone labels, and let
t v = 1 100 ∑ c = 1 100 ( − 1 ) x ( v , c ) . t_v=\frac{1}{100}\sum_{c=1}^{100}(-1)^{x(v,c)}. t v = 100 1 c = 1 ∑ 100 ( − 1 ) x ( v , c ) . First choose clones independently, without conditioning on distinctness. The satisfaction probability of occurrence e e e
1 + ( − 1 ) b e t v e , 1 t v e , 2 t v e , 3 2 . \frac{1+(-1)^{b_e}t_{v_{e,1}}t_{v_{e,2}}t_{v_{e,3}}}{2}. 2 1 + ( − 1 ) b e t v e , 1 t v e , 2 t v e , 3 . Round each bias to a majority label, resolving zero biases arbitrarily. For every equation violated by this rounded assignment, the signed product in the numerator is nonpositive, so its satisfaction probability is at most 1 / 2 1/2 1/2 ( 1 + OPT ( E ) ) / 2 (1 + \operatorname{OPT}(\mathcal{E}))/2 ( 1 + OPT ( E )) /2 3 / 100 3/100 3/100 [ 0 , 1 ] [0,1] [ 0 , 1 ] 3 / 100 3/100 3/100
For the rest of the construction, E \mathcal{E} E ordinary equation-versus-variable game samples e e e ω \omega ω j j j [ 3 ] [3] [ 3 ] e e e v e , j v_{e,j} v e , j j j j
For any second-prover strategy, its bits constitute a global assignment. On an equation violated by that assignment, every valid first-prover answer disagrees in at least one position. Hence this ordinary projection game, denoted G E G_{\mathcal{E}} G E
val ( G E ) ≤ 1 − 1 − OPT ( E ) 3 ≤ 14 15 if OPT ( E ) ≤ 4 5 . (12) \operatorname{val}(G_{\mathcal{E}}) \le1 - \frac{1-\operatorname{OPT}(\mathcal{E})}{3} \le\frac{14}{15}\quad\text{if }\operatorname{OPT}(\mathcal{E}) \le\frac{4}{5}. \tag*{(12)} val ( G E ) ≤ 1 − 3 1 − OPT ( E ) ≤ 15 14 if OPT ( E ) ≤ 5 4 . (12) The answer alphabets have sizes four and two, respectively.
Tuples, local answer copies, and homogeneous coordinates
Fix a positive integer k k k U = ( e 1 , … , e k ) U = (e_1,\ldots,e_k) U = ( e 1 , … , e k ) ω × k \omega^{\times k} ω × k k k k
For a parameter 0 < β < 1 0 < \beta< 1 0 < β < 1 1 − β 1-\beta 1 − β β \beta β O O O π \pi π U U U O O O O O O
Represent an equation answer by its first two bits ( x i , y i ) (x_i,y_i) ( x i , y i ) b e i + x i + y i b_{e_i}+x_i+y_i b e i + x i + y i t 0 t_0 t 0
L U = F 2 1 + 2 k , m = 1 + 2 k , L_U = \mathbb{F}_2^{1+2k},\qquad m = 1+2k, L U = F 2 1 + 2 k , m = 1 + 2 k , and L O L_O L O e 0 T e_0^T e 0 T
The affine projection π \pi π π ‾ : L U → L O \overline{\pi}:L_U\to L_O π : L U → L O t 0 t_0 t 0
{ x i , position 1 , y i , position 2 , b e i t 0 + x i + y i , position 3 . (13) \begin{cases}
x_i, & \text{position 1},\\
y_i, & \text{position 2},\\
b_{e_i}t_0+x_i+y_i, & \text{position 3}. \tag*{(13)}
\end{cases} ⎩ ⎨ ⎧ x i , y i , b e i t 0 + x i + y i , position 1 , position 2 , position 3 . (13) We call every map obtained by these blockwise choices a permitted projection ; this class of maps is independent of β \beta β t 0 t_0 t 0
Exact table keys and folding
The identification of tables across projected questions follows the virtual-table approach of Khot–Safra [28 ] , Section 1.1. We first express each table on the coordinates through which it factors. This will give the same representation to a projected table and its pullback.
Fix latent data ( V , K , C , μ ) (\mathcal{V}, K, C, \mu) ( V , K , C , μ ) K = F 2 2 K = \mathbb{F}_2^2 K = F 2 2 V = K ⊕ W \mathcal{V} = K \oplus W V = K ⊕ W table on a question Q Q Q V \mathcal{V} V P ∈ Hom ( L Q , V ) P \in\operatorname{Hom}(L_Q, \mathcal{V}) P ∈ Hom ( L Q , V ) Q Q Q c c c t 0 t_0 t 0 P P P
In an equation block, inspect the rank of its slope map F 2 2 → V \mathbb{F}_2^2 \to\mathcal{V} F 2 2 → V a i x i + d i y i a_i x_i + d_i y_i a i x i + d i y i
( a i , d i ) = ( v , 0 ) , ( 0 , v ) , ( v , v ) , v ≠ 0. (a_i,d_i) = (v,0), \quad(0,v), \quad(v,v), \quad v \ne0. ( a i , d i ) = ( v , 0 ) , ( 0 , v ) , ( v , v ) , v = 0. These forms retain only the variable at position one, two, or three, respectively, with contribution v z i v z_i v z i z i z_i z i
v ( x i + y i ) = v z i + b e i v t 0 , z i = b e i t 0 + x i + y i , v(x_i+y_i) = v z_i + b_{e_i} v t_0, \qquad z_i = b_{e_i} t_0 + x_i + y_i, v ( x i + y i ) = v z i + b e i v t 0 , z i = b e i t 0 + x i + y i , so this replacement also adds b e i v b_{e_i}v b e i v
The retained blocks form the support of ( Q , P ) (Q,P) ( Q , P ) [ k ] [k] [ k ]
Let J 3 J_3 J 3 v i v_i v i reduced table P ~ \widetilde{P} P
c ~ = c + ∑ i ∈ J 3 b e i v i . (14) \widetilde{c} = c + \sum_{i \in J_3} b_{e_i} v_i. \tag*{(14)} c = c + i ∈ J 3 ∑ b e i v i . (14) To check the complete table, let L s u p p L_{\mathrm{supp}} L supp ρ Q , P : L Q → L s u p p \rho_{Q,P}: L_Q \to L_{\mathrm{supp}} ρ Q , P : L Q → L supp t 0 t_0 t 0 Q Q Q (13) on a reduced equation, and discards omitted blocks. Choosing the coordinates independently in each block shows that ρ Q , P \rho_{Q,P} ρ Q , P (14) give
P = P ~ ρ Q , P . P = \widetilde{P}\rho_{Q,P}. P = P ρ Q , P . Surjectivity makes P ~ \widetilde{P} P key of ( Q , P ) (Q,P) ( Q , P )
We next check compatibility with every permitted projection π ˉ : L U → L O \bar{\pi}: L_U \to L_O π ˉ : L U → L O P ′ ∈ Hom ( L O , V ) P' \in\operatorname{Hom}(L_O, \mathcal{V}) P ′ ∈ Hom ( L O , V ) O O O P ′ P' P ′ P ′ π ˉ P'\bar{\pi} P ′ π ˉ v v v b e i v b_{e_i}v b e i v b e i v b_{e_i}v b e i v F 2 \mathbb{F}_2 F 2 ( U , P ′ π ˉ ) (U, P'\bar{\pi}) ( U , P ′ π ˉ ) ( O , P ′ ) (O, P') ( O , P ′ )
Define the key universe to consist of the keys of all tables on equation questions U ∈ E k U \in\mathcal{E}^k U ∈ E k U U U
We now apply the folding principle of Bellare, Goldreich, and Sudan [7 ] : values on one representative determine the values on its translates. Adding a constant h ∈ K h \in K h ∈ K h h h P P P P + h e 0 ⊤ P + he_0^\top P + h e 0 ⊤ K K K
For a table P P P Q Q Q c ( Q , P ) ∈ K c(Q, P) \in K c ( Q , P ) ∈ K K K K v ( Q , P ) v(Q, P) v ( Q , P ) λ \lambda λ
F Q ( P ) = λ ( v ( Q , P ) ) + c ( Q , P ) . F_Q(P) = \lambda(v(Q, P)) + c(Q, P). F Q ( P ) = λ ( v ( Q , P )) + c ( Q , P ) . Adding a constant changes only the removed component, so
F Q ( P + h e 0 ⊤ ) = F Q ( P ) + h ( h ∈ K ) . F_Q(P + he_0^\top) = F_Q(P) + h \qquad(h \in K). F Q ( P + h e 0 ⊤ ) = F Q ( P ) + h ( h ∈ K ) . Tables with the same key have the same representative and removed component. The pullback compatibility therefore gives, for every permitted U U U O O O π ˉ \bar{\pi} π ˉ P ′ P' P ′ O O O
F U ( P ′ π ˉ ) = F O ( P ′ ) . (15) F_U(P'\bar{\pi}) = F_O(P'). \tag*{(15)} F U ( P ′ π ˉ ) = F O ( P ′ ) . (15) Projected questions thus use answers determined by the same vertex labeling, without an additional consistency test.
The latent matrix test and completeness
The permutation instance, denoted G \mathcal{G} G
U ∼ ω ⊗ k , P uniform in Hom ( L U , V ) , a ∼ μ , l uniform in F 2 m , U \sim\omega^{\otimes k}, \qquad P \text{ uniform in } \operatorname{Hom}(L_U,V), \qquad a \sim\mu, \qquad l \text{ uniform in } \mathbb{F}_2^m, U ∼ ω ⊗ k , P uniform in Hom ( L U , V ) , a ∼ μ , l uniform in F 2 m , and checks
F U ( P ) = F U ( P + a l ⊤ ) . F_U(P) = F_U(P + al^\top). F U ( P ) = F U ( P + a l ⊤ ) . Here a l ⊤ al^\top a l ⊤ z ↦ a ( l ⊤ z ) z \mapsto a(l^\top z) z ↦ a ( l ⊤ z ) c 0 , c 1 c_0,c_1 c 0 , c 1
λ ( v 1 ) = λ ( v 0 ) + c 0 + c 1 \lambda(v_1) = \lambda(v_0) + c_0 + c_1 λ ( v 1 ) = λ ( v 0 ) + c 0 + c 1 of the fixed alphabet K K K O O O G \mathcal{G} G
Lemma 4.3 (Completeness of the outer matrix test). If E \mathcal{E} E 1 − ξ 1-\xi 1 − ξ
Pr x uniform in V , a ∼ μ [ C ( x + a ) ≠ C ( x ) ] ≤ p ∗ , \Pr_{\substack{x\text{ uniform in }V,\,a\sim\mu}}
\left[C(x+a) \ne C(x)\right] \le p_*, x uniform in V , a ∼ μ Pr [ C ( x + a ) = C ( x ) ] ≤ p ∗ , then
val ( G ) ≥ 1 − k ξ − p ∗ 2 . \operatorname{val}(\mathcal{G}) \ge1-k\xi-\frac{p_*}{2}. val ( G ) ≥ 1 − k ξ − 2 p ∗ . Proof. Fix the near-satisfying global bit assignment. Give every reduced support a valid answer as follows. At a singleton use its global bit. At a retained equation use its first two global bits and set the third to the unique value satisfying the equation. These choices depend only on the support, including its occurrence IDs, and therefore define an answer for every exact key independently of its origin.
At an orbit representative, evaluate its reduced table on this answer and apply C C C C C C K K K C C C (4.4) .
With probability at least 1 − k ξ 1-k\xi 1 − k ξ U U U every table are projections of the same full answer z U ∈ L U z_U \in L_U z U ∈ L U (4.6) are
C ( P z U ) and C ( P z U + a ( l T z U ) ) . C(Pz_U) \quad\text{and} \quad C(Pz_U+a(l^{\mathsf T}z_U)). C ( P z U ) and C ( P z U + a ( l T z U )) . Since z U ≠ 0 z_U \ne0 z U = 0 P z U Pz_U P z U V V V a a a l l l l T z U l^{\mathsf T}z_U l T z U p ∗ / 2 p_*/2 p ∗ /2
Matrix extraction and Fourier decoding
We convert high acceptance of the matrix test into agreement between two strategies for the sparsely projected questions U , O U,O U , O k k k
The inverse shortcode theorem
The structural input describes functions that often keep their value under a uniform rank-one perturbation. Such a function agrees with an affine evaluation on a set obtained by fixing a bounded number of linear combinations of rows and columns.
Write Mat ℓ , m = Hom ( F 2 m , F 2 ℓ ) \operatorname{Mat}_{\ell,m}=\operatorname{Hom}(\mathbb{F}_2^m,\mathbb{F}_2^\ell) Mat ℓ , m = Hom ( F 2 m , F 2 ℓ ) row and column slice is a nonempty set specified by equations
S = { M : d i T M = s i T ( 1 ≤ i ≤ n r ) , M q j = t j ( 1 ≤ j ≤ n c ) } . (16) S=\{M:d_i^{\mathsf T}M=s_i^{\mathsf T}\ (1\le i\le n_r),\quad Mq_j=t_j\ (1\le j\le n_c)\}. \tag*{(16)} S = { M : d i T M = s i T ( 1 ≤ i ≤ n r ) , M q j = t j ( 1 ≤ j ≤ n c )} . (16) where d i ∈ F 2 ℓ d_i\in\mathbb{F}_2^\ell d i ∈ F 2 ℓ s i ∈ F 2 m s_i\in\mathbb{F}_2^m s i ∈ F 2 m q j ∈ F 2 m q_j\in\mathbb{F}_2^m q j ∈ F 2 m t j ∈ F 2 ℓ t_j\in\mathbb{F}_2^\ell t j ∈ F 2 ℓ n r , n c n_r,n_c n r , n c
Theorem 5.1 (Equality soundness for degree-two shortcode). For every η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] an integer r s ≥ 1 r_s\ge1 r s ≥ 1 and an integer ℓ 0 \ell_0 ℓ 0 depending only on η \eta η with the following property. For every ℓ ≥ ℓ 0 \ell\ge\ell_0 ℓ ≥ ℓ 0 there is m 0 = m 0 ( η , ℓ ) m_0=m_0(\eta,\ell) m 0 = m 0 ( η , ℓ ) such that, for every m ≥ m 0 m\ge m_0 m ≥ m 0 and every function f : Mat ℓ , m → F 2 ℓ f:\operatorname{Mat}_{\ell,m}\to\mathbb{F}_2^\ell f : Mat ℓ , m → F 2 ℓ if
Pr M , a , l [ f ( M ) = f ( M + a l T ) ] ≥ η , (17) \Pr_{M,a,l}\left[f(M)=f(M+al^{\mathsf T})\right]\ge\eta, \tag*{(17)} M , a , l Pr [ f ( M ) = f ( M + a l T ) ] ≥ η , (17) then some slice S S S as in Equation (16) , with n r , n c ≤ r s n_r,n_c\le r_s n r , n c ≤ r s and some z ∈ F 2 m z\in\mathbb{F}_2^m z ∈ F 2 m u ∈ F 2 ℓ u\in\mathbb{F}_2^\ell u ∈ F 2 ℓ satisfy
Pr M ∣ S [ f ( M ) = M z + u ] ≥ α . (18) \Pr_{M\mid S}\left[f(M)=Mz+u\right]\ge\alpha. \tag*{(18)} M ∣ S Pr [ f ( M ) = M z + u ] ≥ α . (18) Here M , a ∈ F 2 ℓ M,a \in\mathbb{F}_2^{\ell} M , a ∈ F 2 ℓ l ∈ F 2 m l \in\mathbb{F}_2^{m} l ∈ F 2 m M ∣ S M \mid S M ∣ S f f f
Proof. We derive this consequence from the Grassmann expansion theorem of Khot–Minzer–Safra [25 ] [25, Theorem 1.12 in the 2018 revision], using the matrix chart of Barak–Kothari–Steurer [6 ] [6, Definition 3.2 and Lemmas 3.3–3.7].
The Grassmann graph on an ambient binary space E E E ℓ \ell ℓ ℓ − 1 \ell-1 ℓ − 1 retention of a nonempty vertex set is the probability that a uniform vertex in the set has a uniform neighbor still in the set. The cited theorem says that a set of retention at least a fixed ζ > 0 \zeta>0 ζ > 0
{ L : A 0 ⊆ L ⊆ B 0 } , dim A 0 + codim E B 0 ≤ r . \{L:A_0\subseteq L\subseteq B_0\},\qquad\dim A_0+\operatorname{codim}_E B_0\leq r. { L : A 0 ⊆ L ⊆ B 0 } , dim A 0 + codim E B 0 ≤ r . The density bound and r r r ζ \zeta ζ ℓ \ell ℓ dim E \dim E dim E
Equality acceptance is the average of the retention probabilities of the nonempty fibers f − 1 ( y ) f^{-1}(y) f − 1 ( y ) S S S η \eta η
p 0 = 2 − ℓ + 2 − m − 2 − ℓ − m . p_0=2^{-\ell}+2^{-m}-2^{-\ell-m}. p 0 = 2 − ℓ + 2 − m − 2 − ℓ − m . Choose the dimension thresholds so that p 0 ≤ η / 2 p_0\leq\eta/2 p 0 ≤ η /2 S S S ( η − p 0 ) / ( 1 − p 0 ) ≥ η / 2 (\eta-p_0)/(1-p_0)\geq\eta/2 ( η − p 0 ) / ( 1 − p 0 ) ≥ η /2
For each matrix put
L M = { ( x , M T x ) : x ∈ F 2 ℓ } ⊆ E : = F 2 ℓ ⊕ F 2 m . L_M=\{(x,M^{\mathsf T}x):x\in\mathbb{F}_2^{\ell}\}\subseteq E:=\mathbb{F}_2^{\ell}\oplus\mathbb{F}_2^{m}. L M = {( x , M T x ) : x ∈ F 2 ℓ } ⊆ E := F 2 ℓ ⊕ F 2 m . The map M ↦ L M M\mapsto L_M M ↦ L M C \mathcal{C} C
dim ( L M ∩ L N ) = ℓ − rank ( M − N ) , \dim(L_M\cap L_N)=\ell-\operatorname{rank}(M-N), dim ( L M ∩ L N ) = ℓ − rank ( M − N ) , the neighbors within the chart correspond exactly to nonzero rank-one matrix differences. Each chart vertex has ( 2 ℓ − 1 ) ( 2 m − 1 ) (2^\ell-1)(2^m-1) ( 2 ℓ − 1 ) ( 2 m − 1 ) ( 2 ℓ − 1 ) ( 2 m + 1 − 2 ) (2^\ell-1)(2^{m+1}-2) ( 2 ℓ − 1 ) ( 2 m + 1 − 2 ) F 2 \mathbb{F}_2 F 2 a l T a l^{\mathsf T} a l T S ~ = { L M : M ∈ S } \widetilde{S}=\{L_M:M\in S\} S = { L M : M ∈ S } η / 4 \eta/4 η /4
Apply the expansion theorem with ζ = η / 4 \zeta=\eta/4 ζ = η /4 α \alpha α dim A 0 + codim E B 0 ≤ r s \dim A_0+\operatorname{codim}_E B_0\leq r_s dim A 0 + codim E B 0 ≤ r s C \mathcal{C} C S ~ \widetilde{S} S S ~ ⊆ C \widetilde{S}\subseteq\mathcal{C} S ⊆ C ( d i , s i ) (d_i,s_i) ( d i , s i ) A 0 A_0 A 0 A 0 ⊆ L M A_0\subseteq L_M A 0 ⊆ L M d i T M = s i T d_i^{\mathsf T}M=s_i^{\mathsf T} d i T M = s i T E E E ( t j , q j ) (t_j,q_j) ( t j , q j ) B 0 ⊥ B_0^\perp B 0 ⊥ L M ⊆ B 0 L_M\subseteq B_0 L M ⊆ B 0 M q j = t j Mq_j=t_j M q j = t j r s r_s r s α \alpha α f f f S S S z = 0 z=0 z = 0 u u u
The constants α , r s \alpha,r_s α , r s η \eta η dim E = ℓ + m \dim E=\ell+m dim E = ℓ + m ℓ \ell ℓ m 0 ( η , ℓ ) m_0(\eta,\ell) m 0 ( η , ℓ ) [6 ] , Lemma 2.3; numbered references to that paper use its arXiv version 1.
The constants and dimension thresholds in Theorem 5.1 can be chosen effectively, with rational α \alpha α η \eta η [25 ] and the comparison estimates in [25 ] , with theorem numbers again referring to the 2018 revision.
We now fix the parameters needed below. Choose p ∗ > 0 p_\ast> 0 p ∗ > 0 r ∗ r_\ast r ∗
η = 2 − r ∗ / 16 , 2 − ( ℓ − r s ) < α / 8 , 2 − ℓ < η / 4 , (19) \eta= 2^{-r_\ast}/16,\qquad2^{-(\ell-r_s)} < \alpha/8,\qquad2^{-\ell} < \eta/4, \tag*{(19)} η = 2 − r ∗ /16 , 2 − ( ℓ − r s ) < α /8 , 2 − ℓ < η /4 , (19) where α , r s \alpha,r_s α , r s ℓ \ell ℓ ( V , K , C , μ ) (\mathcal{V},K,C,\mu) ( V , K , C , μ ) ℓ \ell ℓ V = K ⊕ W \mathcal{V} = K \oplus W V = K ⊕ W k k k ℓ > r s \ell> r_s ℓ > r s P = ( M , T ) P = (M,T) P = ( M , T ) M : L U → K M : L_U \to K M : L U → K T : L U → W T : L_U \to W T : L U → W
The advice experiment and the decoding statement
We first specify the local inputs for two strategies whose answer agreement will contradict the outer-game gap. This experiment is defined for every positive integer k k k 0 < β < 1 0 < \beta< 1 0 < β < 1 Q k \mathcal{Q}_k Q k U ∈ E k U \in\mathcal{E}^k U ∈ E k O O O U , O U,O U , O π ˉ : L U → L O \bar{\pi} : L_U \to L_O π ˉ : L U → L O 1 − β 1-\beta 1 − β β \beta β
Definition 5.2 (Projected advice experiment). Sample U , O , π U,O,\pi U , O , π A : K → F 2 s A : K \to\mathbb{F}_2^s A : K → F 2 s
T O : L O → W , M O : L O → K . T_O : L_O \to W,\qquad M_O : L_O \to K. T O : L O → W , M O : L O → K . Put S O = A M O S_O = AM_O S O = A M O
U -prover : ( U , A , T O π , S O π ˉ ) , O -prover : ( O , A , T O , S O ) . (20) \begin{aligned}
U\text{-prover}:&\quad(U,A,T_O\pi,S_O\bar{\pi}),\\
O\text{-prover}:&\quad(O,A,T_O,S_O). \tag*{(20)}
\end{aligned} U -prover : O -prover : ( U , A , T O π , S O π ˉ ) , ( O , A , T O , S O ) . (20) The map M O M_O M O a U , a O a_U,a_O a U , a O π ˉ a U = a O \bar{\pi}a_U = a_O π ˉ a U = a O
The U U U ( T U , S U ) = ( T O π , S O π ˉ ) (T_U,S_U) = (T_O\pi,S_O\bar{\pi}) ( T U , S U ) = ( T O π , S O π ˉ ) O O O ( M , T ) (M,T) ( M , T ) U U U S U = A M S_U = AM S U = A M ( M O π , T O π ˉ ) (M_O\pi,T_O\bar{\pi}) ( M O π , T O π ˉ )
Proposition 5.3 (Matrix decoding). Choose the latent and shortcode parameters in the order specified by (19) , fixing V = K ⊕ W \mathcal{V} = K \oplus W V = K ⊕ W k k k γ > 0 \gamma> 0 γ > 0 k 0 ≥ 8 k_0 \ge8 k 0 ≥ 8
For every cube k ≥ k 0 k \ge k_0 k ≥ k 0
F Q : Hom ( L Q , V ) → K F_Q : \operatorname{Hom}(L_Q,\mathcal{V}) \to K F Q : Hom ( L Q , V ) → K is given for every Q ∈ Q k Q \in\mathcal{Q}_k Q ∈ Q k Q Q Q P ∈ Hom ( L Q , V ) P \in\operatorname{Hom}(L_Q,\mathcal{V}) P ∈ Hom ( L Q , V ) c ∈ K c \in K c ∈ K π ˉ : L U → L O \bar{\pi} : L_U \to L_O π ˉ : L U → L O P ′ ∈ Hom ( L O , V ) P' \in\operatorname{Hom}(L_O,\mathcal{V}) P ′ ∈ Hom ( L O , V )
F Q ( P + c θ 0 T ) = F Q ( P ) + c , F U ( P ′ π ˉ ) = F O ( P ′ ) . (21) \begin{aligned}
F_Q(P+c\theta_0^{\mathsf T}) &= F_Q(P)+c,\\
F_U(P'\bar{\pi}) &= F_O(P'). \tag*{(21)}
\end{aligned} F Q ( P + c θ 0 T ) F U ( P ′ π ˉ ) = F Q ( P ) + c , = F O ( P ′ ) . (21) If this family passes the table test of Equation (4.6) with probability at least 0.99, then the projected advice experiment with β = k − 2 / 3 \beta= k^{-2/3} β = k − 2/3 γ \gamma γ
Every labeling of the vertices of G \mathcal{G} G (21) by Equations (4.4) and (15) . The abstract formulation records that no other property of the vertex construction enters the decoding argument. The family is fixed when the two response rules are defined and may be built into those rules.
The next two subsections work for any positive integer k k k (21) . They use unrestricted uniform tables on U U U β \beta β k k k β \beta β
Comparing the two matrix perturbations
The uniform matrix perturbation has the rank-indexed Fourier spectrum computed in [25 ] , Lemma 2.10 in the 2018 revision. We compare that spectrum with the noise supplied by the latent gadget.
Lemma 5.4 (Spectral comparison). If the table family passes Equation (4.6) with probability at least 0.99, then
E U , T Pr M , a , l [ F U ( M , T ) = F U ( M + a l T , T ) ] ≥ 0.9 2 − r ∗ , (22) \mathbb{E}_{U,T}\Pr_{M,a,l}\left[F_U(M,T)=F_U\left(M+al^{\mathsf{T}},T\right)\right]\ge0.9\,2^{-r_*}, \tag*{(22)} E U , T M , a , l Pr [ F U ( M , T ) = F U ( M + a l T , T ) ] ≥ 0.9 2 − r ∗ , (22) where a a a K K K 10 η 10\eta 10 η ( U , T ) (U,T) ( U , T ) 4 η 4\eta 4 η
Proof. For σ ∈ K ∗ \sigma\in K^* σ ∈ K ∗ f U , σ ( P ) = ( − 1 ) σ ( F U ( P ) ) f_{U,\sigma}(P)=(-1)^{\sigma(F_U(P))} f U , σ ( P ) = ( − 1 ) σ ( F U ( P )) g = ( g i ) i = 0 m − 1 g=(g_i)_{i=0}^{m-1} g = ( g i ) i = 0 m − 1 V ∗ \mathcal{V}^* V ∗ P P P ( − 1 ) ∑ i g i ( P e i ) (-1)^{\sum_i g_i(Pe_i)} ( − 1 ) ∑ i g i ( P e i ) a l T al^{\mathsf{T}} a l T ( − 1 ) ∑ i l i g i ( a ) (-1)^{\sum_i l_i g_i(a)} ( − 1 ) ∑ i l i g i ( a ) l l l
Λ g = Pr a ∼ μ [ g i ( a ) = 0 for every i ] . \Lambda_g=\Pr_{a\sim\mu}\left[g_i(a)=0\text{ for every }i\right]. Λ g = a ∼ μ Pr [ g i ( a ) = 0 for every i ] . It lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] 7 / 8 7/8 7/8
dim span { g i ∣ K : 0 ≤ i < m } ≥ r ∗ . \dim\operatorname{span}\{g_i|_K:0\le i<m\}\ge r_*. dim span { g i ∣ K : 0 ≤ i < m } ≥ r ∗ . Indeed the span of the g i g_i g i V ∗ \mathcal{V}^* V ∗
Expanding equality by a uniform output character, and then using Fourier orthogonality, expresses the test acceptance as
E U , σ ∑ g ∣ f ^ U , σ ( g ) ∣ 2 Λ g . \mathbb{E}_{U,\sigma}\sum_g\left|\widehat{f}_{U,\sigma}(g)\right|^2\Lambda_g. E U , σ g ∑ f U , σ ( g ) 2 Λ g . Parseval gives total squared mass one for each sign function. If B B B r ∗ r_* r ∗ 0.99 ≤ 1 − B / 8 0.99\le1-B/8 0.99 ≤ 1 − B /8 B ≤ 0.08 B\le0.08 B ≤ 0.08 0.9 0.9 0.9 r ∗ r_* r ∗
When a a a K K K g g g 2 − dim span { g i ∣ K } 2^{-\dim\operatorname{span}\{g_i|_K\}} 2 − d i m span { g i ∣ K } (22) . This perturbation leaves T T T ( U , T ) (U,T) ( U , T ) 14.4 η 14.4\eta 14.4 η q q q 4 η 4\eta 4 η 4 η + q 4\eta+q 4 η + q q ≥ 10.4 η ≥ 10 η q\ge10.4\eta\ge10\eta q ≥ 10.4 η ≥ 10 η □ \square □
Obtaining many useful row fibers
The inverse theorem gives one structured slice on each qualifying ( U , T ) (U,T) ( U , T ) U U U K K K ( A , A M ) (A,AM) ( A , A M )
For this extraction step, sample U U U T : L U → W T:L_U\to W T : L U → W A : K → F 2 r A:K\to\mathbb{F}_2^r A : K → F 2 r M : L U → K M:L_U\to K M : L U → K U , T , A U,T,A U , T , A S 0 : L U → F 2 r S_0:L_U\to\mathbb{F}_2^r S 0 : L U → F 2 r { M : A M = S 0 } \{M:AM=S_0\} { M : A M = S 0 } ( U , T , A , S 0 ) (U,T,A,S_0) ( U , T , A , S 0 ) r s r_s r s M z + u Mz+u M z + u A M = S 0 AM=S_0 A M = S 0 F U ( M , T ) = M z + u F_U(M,T)=Mz+u F U ( M , T ) = M z + u α / 2 \alpha/2 α /2
This is an analytic condition on the row fiber. The target vector z z z z z z u u u U U U
Lemma 5.5 (Good row advice and its short answer set). For all sufficiently large k k k 0.99 0.99 0.99
Pr U , T , A , M [ ( U , T , A , A M ) is good ] ≥ g 0 , g 0 = 10 η 2 2 − ℓ r s > 0. (23) \Pr_{U,T,A,M}\bigl[(U,T,A,AM)\text{ is good}\bigr]\ge g_0,\qquad g_0=10\eta^2 2^{-\ell r_s}>0. \tag*{(23)} U , T , A , M Pr [ ( U , T , A , A M ) is good ] ≥ g 0 , g 0 = 10 η 2 2 − ℓ r s > 0. (23) The lower bound and the required largeness of k k k
For every positive integer k k k (21) , one can select deterministically for each good row advice at most r s r_s r s M q j = t j Mq_j=t_j M q j = t j q j ∈ L U q_j\in L_U q j ∈ L U t j ∈ K t_j\in K t j ∈ K M z + u Mz+u M z + u z ∈ L U z\in L_U z ∈ L U u ∈ K u\in K u ∈ K e 0 T z = 1 e_0^{\mathsf T}z=1 e 0 T z = 1 Z = span { q j } Z=\operatorname{span}\{q_j\} Z = span { q j }
A = ( z + Z ) ∩ { v ∈ L U : e 0 T v = 1 } , 1 ≤ ∣ A ∣ ≤ 2 r s . (24) \mathcal{A}=(z+Z)\cap\{v\in L_U:e_0^{\mathsf T}v=1\},\qquad1\leq|\mathcal{A}|\leq2^{r_s}. \tag*{(24)} A = ( z + Z ) ∩ { v ∈ L U : e 0 T v = 1 } , 1 ≤ ∣ A ∣ ≤ 2 r s . (24) The witness and A \mathcal{A} A ( U , T , A , S 0 ) (U,T,A,S_0) ( U , T , A , S 0 )
Proof. Fix ( U , T ) (U,T) ( U , T ) 4 η 4\eta 4 η f ( M ) = F U ( M , T ) f(M)=F_U(M,T) f ( M ) = F U ( M , T ) B B B A , S 0 A,S_0 A , S 0 η \eta η f f f B B B K K K 2 Pr [ B ] 2\Pr[B] 2 Pr [ B ] 2 η 2\eta 2 η
We show that the random replacements can be chosen so that they contribute less than α / 4 \alpha/4 α /4 M z + u Mz+u M z + u r = r s r=r_s r = r s r r r r r r
Hom ( F 2 m / span { q j } , ⋂ i ker d i T ) . \operatorname{Hom}\left(\mathbb{F}_2^m/\operatorname{span}\{q_j\},\ \bigcap_i\ker d_i^{\mathsf T}\right). Hom ( F 2 m / span { q j } , i ⋂ ker d i T ) . Its size n S n_{\mathcal S} n S 2 ( ℓ − r ) ( m − r ) 2^{(\ell-r)(m-r)} 2 ( ℓ − r ) ( m − r ) 2 ( 2 r + 1 ) ( ℓ + m ) 2^{(2r+1)(\ell+m)} 2 ( 2 r + 1 ) ( ℓ + m ) [ 0 , 1 ] [0,1] [ 0 , 1 ] 2 − ℓ n S < α n S / 8 2^{-\ell}n_S < \alpha n_S/8 2 − ℓ n S < α n S /8 [19 ] [Theorem 2, equation (2.6)] bounds the probability of at least α n S / 4 \alpha n_S/4 α n S /4 exp ( − α 2 n S / 32 ) \exp(-\alpha^2 n_S/32) exp ( − α 2 n S /32 )
exp ( ( 2 r + 1 ) ( ℓ + m ) log 2 − α 2 32 2 ( ℓ − r ) ( m − r ) ) , \exp\left((2r+1)(\ell+m)\log2-\frac{\alpha^2}{32}2^{(\ell-r)(m-r)}\right), exp ( ( 2 r + 1 ) ( ℓ + m ) log 2 − 32 α 2 2 ( ℓ − r ) ( m − r ) ) , which tends to zero as m = 1 + 2 k m=1+2k m = 1 + 2 k
Consider any slice of the allowed type. If its row fiber was good, every entry of that fiber belongs to B B B α / 4 \alpha/4 α /4 α / 2 \alpha/2 α /2 α / 4 \alpha/4 α /4 3 α / 4 3\alpha/4 3 α /4 2 η 2\eta 2 η
It follows that Pr [ B ] ≥ η \Pr[B]\ge\eta Pr [ B ] ≥ η M ∈ B M\in B M ∈ B A A A M M M A A A 2 − ℓ r S 2^{-\ell r_S} 2 − ℓ r S ( U , T ) (U,T) ( U , T ) η 2 − ℓ r S \eta2^{-\ell r_S} η 2 − ℓ r S 10 η 10\eta 10 η ( U , T ) (U,T) ( U , T ) (23) . All counting and concentration bounds depended only on the fixed parameters and m m m
The remaining assertion does not use high test acceptance or largeness of k k k k k k (21) , and any good row advice. Fix a witness, write its column specifications as M q j = t j M_{q_j}=t_j M q j = t j Z = span { q j } Z=\operatorname{span}\{q_j\} Z = span { q j } t : Z → K t:Z\to K t : Z → K t ( w ) = M w t(w)=M_w t ( w ) = M w z z z z + w z+w z + w u u u u + t ( w ) u+t(w) u + t ( w ) w ∈ Z w\in Z w ∈ Z z + Z z+Z z + Z
Otherwise z z z Z Z Z H = ker A H=\ker A H = ker A h ∈ H h\in H h ∈ H M ↦ M + h e 0 ⊤ M\mapsto M+he_0^{\top} M ↦ M + h e 0 ⊤ F U ( M , T ) F_U(M,T) F U ( M , T ) h h h H H H
∣ H ∣ − 1 = 2 − ℓ + rank A ≤ 2 − ( ℓ − r S ) < α / 8 , |H|^{-1}=2^{-\ell+\operatorname{rank} A}\le2^{-(\ell-r_S)}<\alpha/8, ∣ H ∣ − 1 = 2 − ℓ + rank A ≤ 2 − ( ℓ − r S ) < α /8 , contradicting goodness. Choose w ∈ Z w\in Z w ∈ Z z + w z+w z + w z z z u u u z z z A A A dim Z ≤ r S \dim Z\le r_S dim Z ≤ r S 2 r S 2^{r_S} 2 r S □ \square □
Transferring the chosen slice
The comparison with sparsely projected questions follows the smooth outer-game method of Khot–Safra [28 ] [Section 3 and Lemma 3.1], with shared linear advice as in Khot–Minzer–Safra [26 ] [Sections 3.3–3.4]. Lemma 5.5 gives a positive probability of row advice that determines a slice and a short set of valid answers under unrestricted sampling on U U U O O O U U U O O O
From now on take k k k β = k − 2 / 3 \beta= k^{-2/3} β = k − 2/3 β = k − 2 / 3 \beta= k^{-2/3} β = k − 2/3 k β 2 → 0 k\beta^2 \to0 k β 2 → 0 k β → ∞ k\beta\to\infty k β → ∞
Lemma 5.6 (The padded matrix is asymptotically uniform). Conditional on every U U U
( M , T ) = ( M O π ˉ , T O π ˉ ) (M,T)=(M_{O\bar{\pi}},T_{O\bar{\pi}}) ( M , T ) = ( M O π ˉ , T O π ˉ ) has total variation distance o ( 1 ) o(1) o ( 1 ) Hom ( L U , K ) × Hom ( L U , W ) \operatorname{Hom}(L_U,K)\times\operatorname{Hom}(L_U,W) Hom ( L U , K ) × Hom ( L U , W ) k k k U U U
Proof. Combine the two components into a V \mathcal{V} V n = ∣ V ∣ n=|\mathcal{V}| n = ∣ V ∣ V \mathcal{V} V
( a , 0 ) , ( 0 , a ) , ( a , a ) , a uniform in V . (a,0),\qquad(0,a),\qquad(a,a),\qquad a\text{ uniform in }\mathcal{V}. ( a , 0 ) , ( 0 , a ) , ( a , a ) , a uniform in V . Call these pair laws P 0 P_0 P 0 Q 0 Q_0 Q 0 d Q 0 / d P 0 dQ_0/dP_0 d Q 0 / d P 0 n n n ( 0 , 0 ) (0,0) ( 0 , 0 ) n / 3 n/3 n /3 3 ( n − 1 ) 3(n-1) 3 ( n − 1 )
χ 2 ( Q 0 ∥ P 0 ) : = E P 0 [ ( d Q 0 d P 0 − 1 ) 2 ] = n − 1 3 . \chi^2(Q_0\mathbin\Vert P_0):=\mathbb{E}_{P_0}\left[\left(\frac{dQ_0}{dP_0}-1\right)^2\right]=\frac{n-1}{3}. χ 2 ( Q 0 ∥ P 0 ) := E P 0 [ ( d P 0 d Q 0 − 1 ) 2 ] = 3 n − 1 . The one-block mixture ( 1 − β ) P 0 + β Q 0 (1-\beta)P_0+\beta Q_0 ( 1 − β ) P 0 + β Q 0 β 2 ( n − 1 ) / 3 \beta^2(n-1)/3 β 2 ( n − 1 ) /3 P 0 P_0 P 0
( 1 + n − 1 3 β 2 ) k − 1 = o ( 1 ) , \left(1+\frac{n-1}{3}\beta^2\right)^k-1=o(1), ( 1 + 3 n − 1 β 2 ) k − 1 = o ( 1 ) , because n n n k β 2 = k − 1 / 3 k\beta^2=k^{-1/3} k β 2 = k − 1/3
For a projection onto the third bit of equation e e e b e a b_ea b e a a a a V \mathcal{V} V (5.10) depend on the equation IDs or their right-hand sides. □
Fix good U U U A \mathcal{A} A z ′ = π ˉ z z'=\bar{\pi}z z ′ = π ˉ z Z ′ = π ˉ Z Z'=\bar{\pi}Z Z ′ = π ˉ Z π ˉ \bar{\pi} π ˉ
π ˉ A = ( z ′ + Z ′ ) ∩ { v ∈ L O : e 0 T v = 1 } . (25) \bar{\pi}\mathcal{A}=(z'+Z')\cap\{v\in L_O:e_0^{\mathsf T}v=1\}. \tag*{(25)} π ˉ A = ( z ′ + Z ′ ) ∩ { v ∈ L O : e 0 T v = 1 } . (25) Indeed, every vector in the coset on the right has a preimage in z + Z z+Z z + Z O O O
The certifying slice does not automatically survive projection. For example, a column condition M q = t Mq=t M q = t M O π ˉ q = t M_{O}\bar{\pi}q=t M O π ˉ q = t π ˉ q = 0 \bar{\pi}q=0 π ˉ q = 0 t ≠ 0 t\ne0 t = 0
For this analysis, write D = ( U , O , π , A , T O , S O ) D=(U,O,\pi,A,T_{O},S_{O}) D = ( U , O , π , A , T O , S O ) M O M_{O} M O A M O = S O AM_{O}=S_{O} A M O = S O
Lemma 5.7 (Transfer of a chosen witness). Suppose the matrix-test acceptance is at least 0.99 0.99 0.99 k k k
γ 1 = α g 0 8 2 − ℓ r s > 0 (26) \gamma_{1}=\frac{\alpha g_{0}}{8}2^{-\ell r_{s}}>0 \tag*{(26)} γ 1 = 8 α g 0 2 − ℓ r s > 0 (26) of the joint data D D D U U U A \mathcal{A} A z ′ = π ˉ z z'=\bar{\pi}z z ′ = π ˉ z
A M O = S O , M O π ˉ q j = t j , AM_{O}=S_{O},\qquad M_{O}\bar{\pi}q_{j}=t_{j}, A M O = S O , M O π ˉ q j = t j , on which
Pr [ F O ( M O , T O ) = M O z ′ + u ∣ A M O = S O , M O π ˉ q j = t j for all j ] ≥ α / 4. (27) \Pr[ F_{O}(M_{O},T_{O})=M_{O}z'+u\mid AM_{O}=S_{O},\ M_{O}\bar{\pi}q_{j}=t_{j}\text{ for all }j]\ge\alpha/4. \tag*{(27)} Pr [ F O ( M O , T O ) = M O z ′ + u ∣ A M O = S O , M O π ˉ q j = t j for all j ] ≥ α /4. (27) The probability in this equation is taken over a uniform matrix in the specified slice.
Proof. First use unrestricted sampling of U , A , M , T U,A,M,T U , A , M , T S 0 = A M S_{0}=AM S 0 = A M J \mathcal{J} J ( U , T , A , S 0 ) (U,T,A,S_{0}) ( U , T , A , S 0 ) M M M M \mathcal{M} M ℓ r s \ell r_{s} ℓ r s
Pr [ J ] ≥ g 0 2 − ℓ r s , Pr [ J ∩ M ] ≥ ( α / 2 ) Pr [ J ] . \Pr[\mathcal{J}]\ge g_{0}2^{-\ell r_{s}},\qquad\Pr[\mathcal{J}\cap\mathcal{M}]\ge(\alpha/2)\Pr[\mathcal{J}]. Pr [ J ] ≥ g 0 2 − ℓ r s , Pr [ J ∩ M ] ≥ ( α /2 ) Pr [ J ] . It follows that
Pr [ J ∩ M ] − ( α / 4 ) Pr [ J ] ≥ α g 0 4 2 − ℓ r s . (28) \Pr[\mathcal{J}\cap\mathcal{M}]-(\alpha/4)\Pr[\mathcal{J}]\ge\frac{\alpha g_{0}}{4}2^{-\ell r_{s}}. \tag*{(28)} Pr [ J ∩ M ] − ( α /4 ) Pr [ J ] ≥ 4 α g 0 2 − ℓ r s . (28) Both events in this expression depend only on ( U , A , M , T ) (U,A,M,T) ( U , A , M , T ) A A A v k = o ( 1 ) v_{k}=o(1) v k = o ( 1 ) (28) changes by at most ( 1 + α / 4 ) v k (1+\alpha/4)v_{k} ( 1 + α /4 ) v k k k k γ 1 \gamma_{1} γ 1
Now condition on D D D M O M_{O} M O A M O = S O AM_{O}=S_{O} A M O = S O U U U p D p_{D} p D p D > 0 p_{D}>0 p D > 0 q D q_{D} q D p D = 0 p_{D}=0 p D = 0 q D = 0 q_{D}=0 q D = 0 p D = 0 p_{D}=0 p D = 0 F U ( M O π ˉ , T O π ˉ ) = F O ( M O , T O ) F_{U}(M_{O}\bar{\pi},T_{O}\bar{\pi})=F_{O}(M_{O},T_{O}) F U ( M O π ˉ , T O π ˉ ) = F O ( M O , T O )
E D [ p D ( q D − α / 4 ) ] ≥ γ 1 . \mathbb{E}_{D}[p_{D}(q_{D}-\alpha/4)]\ge\gamma_{1}. E D [ p D ( q D − α /4 )] ≥ γ 1 . The integrand is nonpositive outside the event consisting of goodness, p D > 0 p_{D}>0 p D > 0 q D ≥ α / 4 q_{D}\ge\alpha/4 q D ≥ α /4 γ 1 \gamma_{1} γ 1 ( U , A , M , T ) (U,A,M,T) ( U , A , M , T ) D D D □ \square □
Decoding the row advice
Extracting an outer strategy from Fourier mass follows the approach of Håstad [18 ] and the Fourier-list method of Khot–Safra [28 ] . Here the projected prover samples squared Fourier mass on its own row fiber. The transferred slice will show that this private sample reaches the projected answer set π ˉ A \bar{\pi}A π ˉ A
We now define both strategies from their separate messages. The joint data and the transferred witness serve only in the analysis of their agreement; the O O O U U U
The U U U a U a_U a U A A A 2 r s 2^{rs} 2 r s
The O O O ( O , A , T O , S O ) (O,A,T_O,S_O) ( O , A , T O , S O ) H = ker A H=\ker A H = ker A M 0 M_0 M 0 A M 0 = S O AM_0=S_O A M 0 = S O M 0 + X M_0+X M 0 + X X = Hom ( L O , H ) X=\operatorname{Hom}(L_O,H) X = Hom ( L O , H ) σ ∈ K ∗ \sigma\in K^* σ ∈ K ∗
f σ ( N ) = ( − 1 ) σ ( F O ( M 0 + N , T O ) ) , N ∈ X . f_\sigma(N)=(-1)^{\sigma(F_O(M_0+N,T_O))}, \qquad N\in X. f σ ( N ) = ( − 1 ) σ ( F O ( M 0 + N , T O )) , N ∈ X . Sample a Fourier frequency Φ ∈ X ∗ \Phi\in X^* Φ ∈ X ∗ ∣ f σ ^ ( Φ ) ∣ 2 |\widehat{f_\sigma}(\Phi)|^2 ∣ f σ ( Φ ) ∣ 2 X ∗ = H ∗ ⊗ L O X^*=H^*\otimes L_O X ∗ = H ∗ ⊗ L O
⟨ φ ⊗ v , N ⟩ = φ ( N v ) . \langle\varphi\otimes v,N\rangle=\varphi(Nv). ⟨ φ ⊗ v , N ⟩ = φ ( N v ) . For h ∈ H h\in H h ∈ H Φ \Phi Φ Φ ( h ) ∈ L O \Phi(h)\in L_O Φ ( h ) ∈ L O σ ∣ H ≠ 0 \sigma|_H\ne0 σ ∣ H = 0 h ∈ H h\in H h ∈ H σ ( h ) = 1 \sigma(h)=1 σ ( h ) = 1 Φ ( h ) \Phi(h) Φ ( h )
This rule always returns an actual answer at frequencies of positive mass. Indeed the folding identity in (21) gives
f σ ( N + h e 0 ⊤ ) = − f σ ( N ) when σ ( h ) = 1. f_\sigma(N+he_0^\top)=-f_\sigma(N) \qquad\text{when }\sigma(h)=1. f σ ( N + h e 0 ⊤ ) = − f σ ( N ) when σ ( h ) = 1. Changing variables in a Fourier coefficient shows that its being nonzero requires ( − 1 ) ⟨ Φ , h e 0 ⊤ ⟩ = − 1 (-1)^{\langle\Phi,he_0^\top\rangle}=-1 ( − 1 ) ⟨ Φ , h e 0 ⊤ ⟩ = − 1 e 0 ⊤ Φ ( h ) = 1 e_0^\top\Phi(h)=1 e 0 ⊤ Φ ( h ) = 1
Figure 3 summarizes the information and private choices of the two decoders. The transferred slice will be used only to analyze their agreement probability.
Figure 3. The two decoders use independent random tapes. Neither receives the sampled M O M_O M O π ˉ \bar{\pi} π ˉ M 0 M_0 M 0 σ ∣ H = 0 \sigma|_H = 0 σ ∣ H = 0
Lemma 5.8 (A transferred slice gives agreement). Fix joint data satisfying Lemma 5.7. Conditional on these data, the two rules just defined, using independent randomness, agree under π ˉ \bar{\pi} π ˉ
2 − ℓ r s ( α / 8 ) 2 2 − r s . (29) 2^{-\ell r_s}(\alpha/8)^2 2^{-r_s}. \tag*{(29)} 2 − ℓ r s ( α /8 ) 2 2 − r s . (29) Proof. Put Z ′ = π ˉ Z Z'=\bar{\pi}Z Z ′ = π ˉ Z dim Z ′ ≤ r s \dim Z'\le r_s dim Z ′ ≤ r s N ∣ Z ′ N|_{Z'} N ∣ Z ′ b : Z ′ → H b:Z'\to H b : Z ′ → H N ∗ N_* N ∗ σ ∈ K ∗ \sigma\in K^* σ ∈ K ∗
C σ = E [ f σ ( N ) ( − 1 ) σ ( N z ′ ) ∣ N ∣ Z ′ = b ] . C_\sigma=\mathbb{E}\left[f_\sigma(N)(-1)^{\sigma(Nz')} \mid N|_{Z'}=b\right]. C σ = E [ f σ ( N ) ( − 1 ) σ ( N z ′ ) ∣ N ∣ Z ′ = b ] . The character expansion of (27) gives
E σ [ ( − 1 ) σ ( M 0 z ′ + u ) C σ ] ≥ α / 4 , so E σ ∣ C σ ∣ ≥ α / 4. \mathbb{E}_{\sigma}\left[(-1)^{\sigma(M_0z'+u)}C_\sigma\right]\ge\alpha/4,\qquad\text{so}\qquad\mathbb{E}_{\sigma}|C_\sigma|\ge\alpha/4. E σ [ ( − 1 ) σ ( M 0 z ′ + u ) C σ ] ≥ α /4 , so E σ ∣ C σ ∣ ≥ α /4. Exactly a fraction 2 − dim H 2^{-\dim H} 2 − d i m H H H H dim H ≥ ℓ − r s \dim H\ge\ell-r_s dim H ≥ ℓ − r s ∣ C σ ∣ ≤ 1 |C_\sigma|\le1 ∣ C σ ∣ ≤ 1 (19) implies
E σ [ 1 { σ ∣ H ≠ 0 } ∣ C σ ∣ ] ≥ α / 8. (30) \mathbb{E}_{\sigma}\left[1_{\{\sigma|_H\ne0\}}|C_\sigma|\right]\ge\alpha/8. \tag*{(30)} E σ [ 1 { σ ∣ H = 0 } ∣ C σ ∣ ] ≥ α /8. (30) The annihilator in X ∗ X^* X ∗ Z ′ Z' Z ′ H ∗ ⊗ Z ′ H^*\otimes Z' H ∗ ⊗ Z ′ θ σ = ( σ ∣ H ) ⊗ z ′ \theta_\sigma=(\sigma|_H)\otimes z' θ σ = ( σ ∣ H ) ⊗ z ′
C σ = ∑ Φ ∈ θ σ + H ∗ ⊗ Z ′ f σ ^ ( Φ ) ( − 1 ) ⟨ Φ + θ σ , N ∗ ⟩ . C_\sigma=\sum_{\Phi\in\theta_\sigma+H^*\otimes Z'}\widehat{f_\sigma}(\Phi)(-1)^{\langle\Phi+\theta_\sigma,N_*\rangle}. C σ = Φ ∈ θ σ + H ∗ ⊗ Z ′ ∑ f σ ( Φ ) ( − 1 ) ⟨ Φ + θ σ , N ∗ ⟩ . This sum has 2 dim H dim Z ′ ≤ 2 ℓ r s 2^{\dim H\dim Z'}\le2^{\ell r_s} 2 d i m H d i m Z ′ ≤ 2 ℓ r s σ \sigma σ (30) that
E σ [ 1 { σ ∣ H ≠ 0 } ∑ Φ ∈ θ σ + H ∗ ⊗ Z ′ ∣ f σ ^ ( Φ ) ∣ 2 ] ≥ 2 − ℓ r s E σ [ 1 { σ ∣ H ≠ 0 } C σ 2 ] ≥ 2 − ℓ r s ( α / 8 ) 2 . \mathbb{E}_{\sigma}\left[1_{\{\sigma|_H\ne0\}}\sum_{\Phi\in\theta_\sigma+H^*\otimes Z'}|\widehat{f_\sigma}(\Phi)|^2\right]\ge2^{-\ell r_s}\mathbb{E}_{\sigma}\left[1_{\{\sigma|_H\ne0\}}C_\sigma^2\right]\ge2^{-\ell r_s}(\alpha/8)^2. E σ [ 1 { σ ∣ H = 0 } Φ ∈ θ σ + H ∗ ⊗ Z ′ ∑ ∣ f σ ( Φ ) ∣ 2 ] ≥ 2 − ℓ r s E σ [ 1 { σ ∣ H = 0 } C σ 2 ] ≥ 2 − ℓ r s ( α /8 ) 2 . This is a lower bound on the probability that the O O O
Every such frequency has the form Φ = ( σ ∣ H ) ⊗ z ′ + Ψ \Phi=(\sigma|_H)\otimes z'+\Psi Φ = ( σ ∣ H ) ⊗ z ′ + Ψ Ψ ∈ H ∗ ⊗ Z ′ \Psi\in H^*\otimes Z' Ψ ∈ H ∗ ⊗ Z ′ h h h
Φ ( h ) = z ′ + Ψ ( h ) ∈ z ′ + Z ′ . \Phi(h)=z'+\Psi(h)\in z'+Z'. Φ ( h ) = z ′ + Ψ ( h ) ∈ z ′ + Z ′ . As already proved, a frequency of positive mass gives first bit one. (25) therefore places the returned vector in π ˉ A \bar{\pi}A π ˉ A U U U A A A 1 / ∣ A ∣ ≥ 2 − r s 1/|A|\ge2^{-r_s} 1/∣ A ∣ ≥ 2 − r s (29) . □ \square □
Proof of Proposition 5.3. Use the two decoders above. Lemma 5.7 supplies a set of joint data of probability at least γ 1 \gamma_1 γ 1
γ = γ 1 2 − ℓ r s ( α / 8 ) 2 2 − r s > 0. \gamma=\gamma_1 2^{-\ell r_s}(\alpha/8)^2 2^{-r_s}>0. γ = γ 1 2 − ℓ r s ( α /8 ) 2 2 − r s > 0. The largeness requirements for k k k □ \square □
Clean coordinates and the soundness gap
Proposition 5.3 converts high acceptance of the matrix test into agreement between two local strategies supplied with correlated linear advice. We now bound the value of this advice experiment on a NO parity instance. The use of vanishing advice is part of the smooth outer-game framework of [26 ] , Sections 3.3–3.4. We give the full local reconstruction argument for the present occurrence-indexed questions. The key is to identify singleton coordinates on which both advice slopes vanish. After fixing the data outside those coordinates, their question pairs have the ordinary independent equation–variable law. Each side can then reconstruct its original advice input from its own remaining questions and the fixed data. This defines strategies for an ordinary parallel repetition, whose value bounds the original agreement.
Classical projection-game repetition
We use the following form of the parallel repetition theorem of Dinur and Steurer. The value here is the ordinary classical value: each prover answers using only its own question. A projection constraint maps each answer on one side to its required answer on the other side.
Theorem 6.1 (Projection-game repetition). Let G G G G ⊗ n G^{\otimes n} G ⊗ n n n n n n n n ≥ 1 n \ge1 n ≥ 1 0 < g < 1 0 < g < 1 0 < g < 1
val ( G ) ≤ 1 − g ⟹ val ( G ⊗ n ) ≤ ( 1 − g 2 / 16 ) n . (31) \operatorname{val}(G) \le1-g \quad\Longrightarrow\quad\operatorname{val}(G^{\otimes n}) \le(1-g^2/16)^n. \tag*{(31)} val ( G ) ≤ 1 − g ⟹ val ( G ⊗ n ) ≤ ( 1 − g 2 /16 ) n . (31) The bound is independent of the question-set and alphabet sizes.
This is Corollary 1.2 of [13 ] . Their Section 2.1 permits nonnegative edge weights and parallel edges, and Section 2.2 defines the independent product used here. Thus the theorem applies to any finite weighted question distribution in our constructions. Interchanging the provers, if necessary, matches the direction of the projection. Private randomization and shared randomness independent of the questions do not increase classical value: sample complete deterministic answer tables using that randomness before the questions arrive, and average their success probabilities.
Vanishing advice on clean coordinates
Let E \mathcal{E} E G E G_{\mathcal{E}} G E (12) gives val ( G E ) ≤ 14 / 15 \operatorname{val}(G_{\mathcal{E}}) \le14/15 val ( G E ) ≤ 14/15
Recall the advice experiment of Section 5, taking k k k β = k − 2 / 3 \beta= k^{-2/3} β = k − 2/3 U U U k k k β \beta β O O O π ~ : L U → L O \widetilde{\pi}: L_U \to L_O π : L U → L O (13) . Independently choose
A : K → F 2 r , T O : L O → W , M O : L O → K A: K \to\mathbb{F}_2^r,\qquad T_O: L_O \to W,\qquad M_O: L_O \to K A : K → F 2 r , T O : L O → W , M O : L O → K uniformly, and put S O = A M O S_O = A M_O S O = A M O
( U , A , T O π ~ , S O π ~ ) and ( O , A , T O , S O ) . (32) (U,A,T_O\widetilde{\pi},S_O\widetilde{\pi})\quad\text{and}\quad(O,A,T_O,S_O). \tag*{(32)} ( U , A , T O π , S O π ) and ( O , A , T O , S O ) . (32) The matrix M O M_O M O S O S_O S O
Lemma 6.2 (Clean-coordinate bound). If OPT ( E ) ≤ 4 / 5 \operatorname{OPT}(\mathcal{E}) \le4/5 OPT ( E ) ≤ 4/5
Pr [ π ‾ ( a U ) = a O ] ≤ ( 1 − β 2 − dim W − r S 3600 ) k ≤ exp ( − 2 − dim W − r S 3600 k 1 / 3 ) . (33) \Pr[\overline{\pi}(a_U)=a_O]\leq\left(1-\frac{\beta2^{-\dim W-r_S}}{3600}\right)^k\leq\exp\left(-\frac{2^{-\dim W-r_S}}{3600}k^{1/3}\right). \tag*{(33)} Pr [ π ( a U ) = a O ] ≤ ( 1 − 3600 β 2 − d i m W − r S ) k ≤ exp ( − 3600 2 − d i m W − r S k 1/3 ) . (33) In particular, the upper bound tends to zero uniformly over the parity instance as k k k
Proof. Fix an arbitrary pair of local randomized strategies in the advice experiment. We first condition on A A A
D O = ( T O , S O ) : L O ⟶ E A , E A = W ⊕ im A . D_O=(T_O,S_O):L_O\longrightarrow E_A,\qquad E_A=W\oplus\operatorname{im} A. D O = ( T O , S O ) : L O ⟶ E A , E A = W ⊕ im A . Conditional on the questions and projection choices, the intercept c O c_O c O D O D_O D O E A E_A E A T O T_O T O M O M_O M O A A A im A \operatorname{im} A im A c O c_O c O
Call coordinate i i i clean if it is projected to a singleton and its one advice slope d i ∈ E A d_i\in E_A d i ∈ E A A A A
p A = β ∣ E A ∣ = β 2 − dim W − rank A . (34) p_A=\frac{\beta}{|E_A|}=\beta2^{-\dim W-\operatorname{rank} A}. \tag*{(34)} p A = ∣ E A ∣ β = β 2 − d i m W − rank A . (34) More precisely, for every equation occurrence e e e j ∈ [ 3 ] j\in[3] j ∈ [ 3 ]
Pr [ e i = e , i is a clean singleton at position j ∣ A ] = ω e β 3 ∣ E A ∣ . (35) \Pr[e_i=e,\ i\text{ is a clean singleton at position }j\mid A]=\omega_e\frac{\beta}{3|E_A|}. \tag*{(35)} Pr [ e i = e , i is a clean singleton at position j ∣ A ] = ω e 3∣ E A ∣ β . (35) Thus, conditional on being clean, a coordinate has precisely the ordinary equation–variable distribution.
Let I ⊆ [ k ] I\subseteq[k] I ⊆ [ k ] R R R A A A I I I c O c_O c O i ∉ I i\notin I i ∈ / I R R R
For each value R = r R=r R = r I I I r r r I I I r r r G E ⊗ ∣ I ∣ G_{\mathcal{E}}^{\otimes|I|} G E ⊗ ∣ I ∣
Conditional on R = r R=r R = r
( e i , v e i , j i ) , i ∈ I , (e_i,v_{e_i,j_i}),\qquad i\in I, ( e i , v e i , j i ) , i ∈ I , are independent question pairs of G E G_{\mathcal{E}} G E A A A (35) shows that conditioning on the clean mask preserves the ordinary law in each clean coordinate. The outside coordinate data and the independent intercept impose no further condition on these pairs.
We now verify the two reconstructions, including the affine intercept shared across the blocks. An equation with right-hand side b e b_e b e x x x y y y b e t 0 + x + y b_e t_0 + x + y b e t 0 + x + y d i d_i d i
( d i , 0 ) , ( 0 , d i ) , ( d i , d i ) (d_i, 0), \quad(0, d_i), \quad(d_i, d_i) ( d i , 0 ) , ( 0 , d i ) , ( d i , d i ) at positions one, two, and three, respectively. The intercept of D U = D O π ˉ D_U = D_O\bar{\pi} D U = D O π ˉ
c U = c O + ∑ i projected to a singleton j i = 3 b e i d i . (36) c_U = c_O + \sum_{\substack{i\ \text{projected to a singleton}\\ j_i=3}} b_{e_i}d_i. \tag*{(36)} c U = c O + i projected to a singleton j i = 3 ∑ b e i d i . (36) For a clean coordinate, every slope in Equation (6.6) is zero and its contribution to Equation (36) is zero. All remaining terms in that equation are determined by r r r
The equation side receives its occurrences e i e_i e i i ∈ I i \in I i ∈ I r r r U U U r r r i ∈ I i \in I i ∈ I r r r O O O r r r
These reconstructions define the promised product-game strategies: each side applies its original response rule to the reconstructed input and retains its answers in the slots I I I I = ∅ I = \varnothing I = ∅
Pr [ π ˉ a U = a O ∣ R = r ] ≤ val ( G E ⊗ ∣ I ∣ ) ≤ ( 1 − 1 3600 ) ∣ I ∣ . \Pr[\bar{\pi}a_U = a_O \mid R = r] \leq\operatorname{val}\left(G_{\mathcal{E}}^{\otimes|I|}\right) \leq\left(1 - \frac{1}{3600}\right)^{|I|}. Pr [ π ˉ a U = a O ∣ R = r ] ≤ val ( G E ⊗ ∣ I ∣ ) ≤ ( 1 − 3600 1 ) ∣ I ∣ . The first inequality uses the strategies just constructed and the conditional product law. The second uses Theorem 6.1 and Equation (12) . The original response rules are evaluated only at their original local inputs; r r r r r r I = ∅ I = \varnothing I = ∅
Finally, conditional on A A A I I I Binomial ( k , p A ) \operatorname{Binomial}(k,p_A) Binomial ( k , p A ) R R R A A A A A A
Pr [ π ˉ ( a U ) = a O ] ≤ E A ( 1 − p A 3600 ) k ≤ ( 1 − β 2 − dim W − r s 3600 ) k ≤ exp ( − k β 2 − dim W − r s 3600 ) , \begin{aligned}
\Pr[\bar{\pi}(a_U) = a_O] \leq\mathbb{E}_A\left(1-\frac{p_A}{3600}\right)^k \\
&\leq\left(1-\frac{\beta2^{-\dim W-r_s}}{3600}\right)^k \\
&\leq\exp\left(-\frac{k\beta2^{-\dim W-r_s}}{3600}\right),
\end{aligned} Pr [ π ˉ ( a U ) = a O ] ≤ E A ( 1 − 3600 p A ) k ≤ ( 1 − 3600 β 2 − d i m W − r s ) k ≤ exp ( − 3600 k β 2 − d i m W − r s ) , since rank A ≤ r s \operatorname{rank} A \leq r_s rank A ≤ r s k β = k 1 / 3 k\beta= k^{1/3} k β = k 1/3 (33) .
The matrix-game gap
We can now compare the upper bound for every advice strategy with the strategies extracted from a highly accepting matrix labeling.
Proposition 6.3 (A fixed gap with adjustable completeness). Fix p ∗ > 0 p_* > 0 p ∗ > 0 latent and shortcode data in the order of (19) . For every sufficiently large cube k k k matrix game G G G E \mathcal{E} E
OPT ( E ) ≥ 1 − ξ ⟹ val ( G ) ≥ 1 − k ξ − p ∗ / 2 , \operatorname{OPT}(\mathcal{E}) \ge1-\xi\quad\Longrightarrow\quad\operatorname{val}(G) \ge1-k\xi-p_*/2, OPT ( E ) ≥ 1 − ξ ⟹ val ( G ) ≥ 1 − k ξ − p ∗ /2 , OPT ( E ) ≤ 4 / 5 ⟹ val ( G ) ≤ 99 / 100. \operatorname{OPT}(\mathcal{E}) \le4/5 \quad\Longrightarrow\quad\operatorname{val}(G) \le99/100. OPT ( E ) ≤ 4/5 ⟹ val ( G ) ≤ 99/100. The lower threshold on k k k E \mathcal{E} E ξ \xi ξ
Proof. Completeness is Lemma 4.3. For soundness, fix a labeling of G G G γ > 0 \gamma> 0 γ > 0 k k k γ \gamma γ 0.99 0.99 0.99 k k k (33) is smaller than γ \gamma γ OPT ( E ) ≤ 4 / 5 \operatorname{OPT}(\mathcal{E}) \le4/5 OPT ( E ) ≤ 4/5 □ \square □
The order matters: p ∗ p_* p ∗ ξ \xi ξ k k k
Completion of the reduction
The matrix game has a fixed soundness gap and an arbitrarily small completeness error. We now obtain the form required by Theorem 1.1: unweighted, simple bipartite games with arbitrary prescribed errors. Rounding the occurrence weights and subdividing each occurrence will preserve a fixed gap. One application of alphabet-independent repetition then completes the proof.
Removing weights and repeated edges
We use the following elementary construction for weighted permutation constraints. At this intermediate stage, a constraint occurrence may be a loop, and several occurrences may join the same vertices.
Lemma 7.1 (Rounding and subdivision). Let H H H h ≥ 1 h \ge1 h ≥ 1 τ \tau τ Q = ⌈ h / τ ⌉ Q = \lceil h/\tau\rceil Q = ⌈ h / τ ⌉ B B B 4 Q 4Q 4 Q
∣ val ( B ) − ( 1 − 1 − val ( H ) 4 ) ∣ ≤ τ 4 . (37) \left|\operatorname{val}(B)-\left(1-\frac{1-\operatorname{val}(H)}{4}\right)\right| \le\frac{\tau}{4}. \tag*{(37)} val ( B ) − ( 1 − 4 1 − val ( H ) ) ≤ 4 τ . (37) If the constraints of H H H B B B τ \tau τ H H H
Proof. Write the occurrence weights as w 1 , … , w h w_1,\ldots,w_h w 1 , … , w h n e = ⌊ Q w e ⌋ n_e = \lfloor Qw_e\rfloor n e = ⌊ Q w e ⌋ Q − ∑ e ⌊ Q w e ⌋ Q-\sum_e\lfloor Qw_e\rfloor Q − ∑ e ⌊ Q w e ⌋
n e ≥ 0 , ∑ e n e = Q , ∣ w e − n e Q ∣ ≤ 1 Q . n_e \ge0,\qquad\sum_e n_e = Q,\qquad\left|w_e-\frac{n_e}{Q}\right| \le\frac{1}{Q}. n e ≥ 0 , e ∑ n e = Q , w e − Q n e ≤ Q 1 . The weight differences sum to zero. Consequently, for every labeling, the change in the weight of its satisfied-occurrence set is at most
1 2 ∑ e = 1 h ∣ w e − n e Q ∣ ≤ h 2 Q ≤ τ . \frac{1}{2}\sum_{e=1}^{h} \left|w_e - \frac{n_e}{Q}\right| \le\frac{h}{2Q} \le\tau. 2 1 e = 1 ∑ h w e − Q n e ≤ 2 Q h ≤ τ . Replace each occurrence e e e n e n_e n e n e = 0 n_e=0 n e = 0 H ′ H' H ′ Q Q Q ∣ val ( H ′ ) − val ( H ) ∣ ≤ τ \lvert\operatorname{val}(H')-\operatorname{val}(H)\rvert\le\tau ∣ val ( H ′ ) − val ( H )∣ ≤ τ
Orient each occurrence e e e H ′ H' H ′ u u u v v v a v = ρ e ( a u ) a_v=\rho_e(a_u) a v = ρ e ( a u )
u − p e − q e − r e − v , u \mathbin{-} p_e \mathbin{-} q_e \mathbin{-} r_e \mathbin{-} v, u − p e − q e − r e − v , using three fresh interior vertices for every occurrence. Place all original vertices and all q e q_e q e p e , r e p_e,r_e p e , r e u u u v v v ρ e \rho_e ρ e 4 Q 4Q 4 Q
Fix labels at the original vertices. A satisfied occurrence extends to four satisfied edges. A violated occurrence cannot extend to four, but propagating labels along the first three edges satisfies exactly three. Since the interiors are disjoint, these extensions can be chosen independently. Maximizing over the original labels gives the exact identity
val ( B ) = 1 − 1 − val ( H ′ ) 4 . (38) \operatorname{val}(B)=1-\frac{1-\operatorname{val}(H')}{4}. \tag*{(38)} val ( B ) = 1 − 4 1 − val ( H ′ ) . (38) This proves (37) .
A loop becomes a four-cycle with three distinct new vertices. Parallel occurrences have disjoint interiors. Thus each left-right vertex pair carries at most one edge, so B B B
Finally, Q ≤ h / τ + 1 Q\le h/\tau+1 Q ≤ h / τ + 1 τ \tau τ n e n_e n e Q Q Q 3 Q 3Q 3 Q
The final reduction
Proof of Theorem 1.1. Fix ε , δ ∈ ( 0 , 1 / 2 ) \varepsilon,\delta\in(0,1/2) ε , δ ∈ ( 0 , 1/2 ) ε 0 ≤ ε \varepsilon_0\le\varepsilon ε 0 ≤ ε δ 0 ≤ δ \delta_0\le\delta δ 0 ≤ δ τ ≤ 1 / 200 \tau\le1/200 τ ≤ 1/200 H H H val ( H ) ≤ 99 / 100 \operatorname{val}(H)\le99/100 val ( H ) ≤ 99/100 B B B
val ( B ) ≤ 1 − 1 / 100 − τ 4 ≤ 1 − 1 800 . (39) \operatorname{val}(B)\le1-\frac{1/100-\tau}{4}\le1-\frac{1}{800}. \tag*{(39)} val ( B ) ≤ 1 − 4 1/100 − τ ≤ 1 − 800 1 . (39) This gap does not depend on the alphabet. We can therefore use alphabet-independent repetition to choose its exponent before the latent construction fixes that alphabet. Choose an integer t ≥ 1 t\ge1 t ≥ 1
( 1 − 1 10240000 ) t ≤ δ 0 . (40) \left(1-\frac{1}{10240000}\right)^t\le\delta_0. \tag*{(40)} ( 1 − 10240000 1 ) t ≤ δ 0 . (40) For example, t ≥ ⌈ 10240000 log ( 1 / δ 0 ) ⌉ t\ge\lceil10240000\log(1/\delta_0)\rceil t ≥ ⌈ 10240000 log ( 1/ δ 0 )⌉ 1 − 1 / 800 1-1/800 1 − 1/800 δ 0 \delta_0 δ 0
Choose positive rational parameters
p ∗ ≤ ε 0 t , τ ≤ min { 1 200 , ε 0 t } . (41) p_\ast\le\frac{\varepsilon_0}{t},\qquad\tau\le\min\left\{\frac{1}{200},\frac{\varepsilon_0}{t}\right\}. \tag*{(41)} p ∗ ≤ t ε 0 , τ ≤ min { 200 1 , t ε 0 } . (41) Choose the latent rank threshold r ∗ r_\ast r ∗ η = 2 − r ∗ / 16 \eta= 2^{-r_\ast}/16 η = 2 − r ∗ /16 α , r s \alpha, r_s α , r s α \alpha α ℓ \ell ℓ (19) , and fix the corresponding latent data ( V , K , C , μ ) (V,K,C,\mu) ( V , K , C , μ ) V = K ⊕ W V = K \oplus W V = K ⊕ W K = F 2 ℓ K = \mathbb{F}_2^\ell K = F 2 ℓ
Once the rational budgets are fixed, these choices are effective. For rational p ∗ p_\ast p ∗ α \alpha α m 0 ( η , ℓ ) m_0(\eta,\ell) m 0 ( η , ℓ ) ℓ \ell ℓ
Next choose a cube k ≥ 8 k \ge8 k ≥ 8 m = 1 + 2 k m = 1 + 2k m = 1 + 2 k β = k − 2 / 3 \beta= k^{-2/3} β = k − 2/3 k k k β \beta β m ≥ m 0 ( η , ℓ ) m \ge m_0(\eta,\ell) m ≥ m 0 ( η , ℓ )
α 2 32 2 ( ℓ − r s ) ( m − r s ) > ( 2 r s + 1 ) ( ℓ + m ) . \frac{\alpha^2}{32}2^{(\ell-r_s)(m-r_s)} > (2r_s+1)(\ell+m). 32 α 2 2 ( ℓ − r s ) ( m − r s ) > ( 2 r s + 1 ) ( ℓ + m ) . The latter is a sufficient rational condition for the union bound in Lemma 5.5 to be less than one. For witness transfer in Lemma 5.7, require
1 4 [ ( 1 + ∣ V ∣ − 1 3 β 2 ) k − 1 ] < γ 1 2 ( 1 + α / 4 ) 2 , \frac{1}{4}\left[\left(1+\frac{|V|-1}{3}\beta^2\right)^k-1\right] < \frac{\gamma_1^2}{(1+\alpha/4)^2}, 4 1 [ ( 1 + 3 ∣ V ∣ − 1 β 2 ) k − 1 ] < ( 1 + α /4 ) 2 γ 1 2 , where γ 1 \gamma_1 γ 1 (26) . The left-hand side is the square of the total-variation bound. For the final contradiction, require
( 1 − β 2 − dim W − r s 3600 ) k < γ , \left(1-\frac{\beta2^{-\dim W-r_s}}{3600}\right)^k < \gamma, ( 1 − 3600 β 2 − d i m W − r s ) k < γ , with γ \gamma γ k k k k k k
Finally, with k k k
ξ < min { 1 100 , ε 0 2 k t } . (42) \xi< \min\left\{\frac{1}{100},\frac{\varepsilon_0}{2kt}\right\}. \tag*{(42)} ξ < min { 100 1 , 2 k t ε 0 } . (42) Every choice depends only on the two prescribed errors. In particular, r ∗ r_\ast r ∗ ℓ \ell ℓ k k k k k k ξ \xi ξ
Given a 3SAT formula, apply Theorem 4.1 and Lemma 4.2, and construct the matrix game H H H
Y E S : val ( H ) ≥ 1 − d , d = k ξ + p ∗ / 2 ≤ ε 0 / t , N O : val ( H ) ≤ 99 / 100. \begin{aligned}
\mathrm{YES:}\quad&\operatorname{val}(H) \ge1-d,\quad d=k\xi+p_\ast/2 \le\varepsilon_0/t,\\
\mathrm{NO:}\quad&\operatorname{val}(H) \le99/100.
\end{aligned} YES : NO : val ( H ) ≥ 1 − d , d = k ξ + p ∗ /2 ≤ ε 0 / t , val ( H ) ≤ 99/100. Apply Lemma 7.1 with τ \tau τ B B B
Y E S : val ( B ) ≥ 1 − ( d + τ ) / 4 , N O : val ( B ) ≤ 1 − 1 / 800 , \begin{aligned}
\mathrm{YES:}\quad&\operatorname{val}(B) \ge1-(d+\tau)/4,\\
\mathrm{NO:}\quad&\operatorname{val}(B) \le1-1/800,
\end{aligned} YES : NO : val ( B ) ≥ 1 − ( d + τ ) /4 , val ( B ) ≤ 1 − 1/800 , where the NO bound is (39) . The final output is G = B ⊗ t G = B^{\otimes t} G = B ⊗ t δ 0 ≤ δ \delta_0 \le\delta δ 0 ≤ δ (31) and (40) . On a YES input, use a labeling of B B B
val ( G ) ≥ 1 − t ( d + τ ) 4 ≥ 1 − ε 0 / 2 ≥ 1 − ε . \operatorname{val}(G) \ge1-\frac{t(d+\tau)}{4} \ge1-\varepsilon_0/2 \ge1-\varepsilon. val ( G ) ≥ 1 − 4 t ( d + τ ) ≥ 1 − ε 0 /2 ≥ 1 − ε . The output has the claimed graph and constraint form. Its two vertex sets are the t t t B B B B B B H H H K K K c 1 , … , c t c_1,\ldots,c_t c 1 , … , c t ( c 1 , … , c t ) (c_1,\ldots,c_t) ( c 1 , … , c t ) K t = F 2 ℓ t K^t = \mathbb{F}_2^{\ell t} K t = F 2 ℓ t F 2 s \mathbb{F}_2^s F 2 s s = ℓ t ≥ 1 s = \ell t \ge1 s = ℓ t ≥ 1
Polynomial encoding. Suppose the preprocessed parity instance has N ε N_\varepsilon N ε N ε k N_\varepsilon^k N ε k h h h N ε k N_\varepsilon^k N ε k k k k
Exact table keys and folded representatives are computed by linear algebra in fixed dimensions, keeping the original variable and occurrence IDs. At most 2 h 2h 2 h Q = ⌈ h / τ ⌉ = O ( h ) Q = \lceil h/\tau\rceil= O(h) Q = ⌈ h / τ ⌉ = O ( h ) 3 Q 3Q 3 Q 4 Q 4Q 4 Q ( 4 Q ) t (4Q)^t ( 4 Q ) t t t t F 2 ℓ t \mathbb{F}_2^{\ell t} F 2 ℓ t O ( t log ( h + 1 ) ) O(t\log(h+1)) O ( t log ( h + 1 ))
Approximation consequences
Theorem 1.1 turns established conditional hardness results into NP-hardness results. The underlying conditional reductions and approximation thresholds are due to the cited authors. We give the additional arguments needed for the exact instance models stated below. We also record two results from companion manuscripts. For a maximization problem, ratio r r r r r r c c c c c c ≠ \ne =
Constraint satisfaction and Vertex Cover
For Max-Cut, which maximizes the number of edges crossing a bipartition, Khot, Kindler, Mossel, and O’Donnell’s reduction gives NP-hardness of approximation at every fixed ratio in ( α G W , 1 ) (\alpha_{\mathrm{GW}},1) ( α GW , 1 ) α G W ≃ 0.87856 \alpha_{\mathrm{GW}} \simeq0.87856 α GW ≃ 0.87856 [24 ] , Theorem 1. This matches the semidefinite approximation threshold of Goemans and Williamson [16 ] . The reduction uses the Majority Is Stablest theorem of Mossel, O’Donnell, and Oleszkiewicz [32 ] . For Vertex Cover, which minimizes the number of vertices meeting every edge, Khot and Regev’s reduction gives NP-hardness at every fixed factor in ( 1 , 2 ) (1,2) ( 1 , 2 ) [27 ] .
A constraint satisfaction problem (CSP) is specified here by a finite nonempty domain D D D Λ \Lambda Λ D D D Λ \Lambda Λ Λ \Lambda Λ D D D [36 ] (Theorem 1.1 and Corollary 1.3). The Vertex Cover result uses its own reduction. Write S D P R \mathrm{SDP}_{R} SDP R [37 ] , Section 4.5.
The fixed-instance form of Raghavendra’s theorem and the ordering theorem below use a strengthened bipartite formulation of Unique Games. In its YES case, one labeling satisfies every edge incident to at least a 1 − ζ 1-\zeta 1 − ζ ν \nu ν [27 ] , Lemmas 3.3, 3.4, and 3.6, with an additional restriction that makes the graph simple. Its error parameters and degree are fixed before the alphabet is chosen, so Theorem 1.1 supplies the required premise.
Corollary 8.1 (Raghavendra’s consequence). Let J J J Λ \Lambda Λ A = OPT ( J ) < B = S D P R ( J ) A = \operatorname{OPT}(J) < B = \mathrm{SDP}_{R}(J) A = OPT ( J ) < B = SDP R ( J ) 0 < η < ( B − A ) / 2 0 < \eta< (B-A)/2 0 < η < ( B − A ) /2 Λ \Lambda Λ I I I
OPT ( I ) ≥ B − η from those satisfying OPT ( I ) ≤ A + η . \operatorname{OPT}(I) \ge B-\eta\qquad\text{from those satisfying} \qquad\operatorname{OPT}(I) \le A+\eta. OPT ( I ) ≥ B − η from those satisfying OPT ( I ) ≤ A + η . Proof. For the thesis’s common-arity convention [37 ] , Definitions 7.2.1–7.2.2, identify D D D [ q ] [q] [ q ] J J J A < B A < B A < B [37 ] , Section 4.5. In that relaxation, each local distribution is over assignments to the variables on which its applied payoff actually depends. When emitting an occurrence, discard only the added trailing positions, retaining the original predicate from Λ \Lambda Λ
Apply Raghavendra’s fixed-instance theorem [37 ] , Theorem 7.9 with tolerance η / 2 \eta/2 η /2 [36 ] , Theorem 1.1 and Lemma 2.3. The fixed witness and tolerance determine its strengthened Unique Games errors, so the formulation above and Theorem 1.1 supply its premise, with a fixed alphabet [ M ] [M] [ M ] B − η / 2 B-\eta/2 B − η /2 A + η / 2 A+\eta/2 A + η /2
We pass from the verifier’s probability weights to the stated rational weights. For this fixed invocation, the construction in [37 ] , Sections 7.3.1 and 7.5 gives a local probability law θ \theta θ S \mathcal{S} S [ M ] [M] [ M ] s ∈ S s \in\mathcal{S} s ∈ S J J J a ( s ) a(s) a ( s ) D M D^M D M J , η , M J,\eta,M J , η , M θ ^ ∈ Q ≥ 0 S \hat{\theta} \in\mathbb{Q}_{\ge0}^{\mathcal{S}} θ ^ ∈ Q ≥ 0 S
∑ s ∈ S θ ^ ( s ) = 1 , δ : = 1 2 ∑ s ∈ S ∣ θ ^ ( s ) − θ ( s ) ∣ < η 2 . \sum_{s\in\mathcal{S}} \hat{\theta}(s)=1,\qquad\delta:= \frac{1}{2}\sum_{s\in\mathcal{S}} \lvert\hat{\theta}(s)-\theta(s)\rvert< \frac{\eta}{2}. s ∈ S ∑ θ ^ ( s ) = 1 , δ := 2 1 s ∈ S ∑ ∣ θ ^ ( s ) − θ ( s )∣ < 2 η . This rational table is fixed finite data of the reduction; its description length may depend on J , η , M J,\eta,M J , η , M
Let L Φ L_{\Phi} L Φ V Φ V_{\Phi} V Φ h ≥ 1 h \ge1 h ≥ 1 V Φ × D M V_{\Phi}\times D^M V Φ × D M u u u u u u s ∈ S s \in\mathcal{S} s ∈ S u ∈ L Φ u \in L_{\Phi} u ∈ L Φ N ( u ) a ( s ) N(u)^{a(s)} N ( u ) a ( s ) Λ \Lambda Λ s s s
θ ^ ( s ) ∣ L Φ ∣ h a ( s ) . \frac{\widehat{\theta}(s)}{|L_{\Phi}|h^{a(s)}}. ∣ L Φ ∣ h a ( s ) θ ( s ) . These weights are nonnegative rationals summing to one. Keeping equal occurrences separate gives ∣ L Φ ∣ ∑ s ∈ S h a ( s ) |L_{\Phi}|\sum_{s\in S}h^{a(s)} ∣ L Φ ∣ ∑ s ∈ S h a ( s ) ∣ V Φ ∣ ∣ D ∣ M |V_{\Phi}||D|^{M} ∣ V Φ ∣∣ D ∣ M a ( s ) a(s) a ( s ) ∣ L Φ ∣ h a ( s ) |L_{\Phi}|h^{a(s)} ∣ L Φ ∣ h a ( s )
For an assignment σ \sigma σ g σ ( s ) ∈ [ 0 , 1 ] g_{\sigma}(s)\in[0,1] g σ ( s ) ∈ [ 0 , 1 ]
∣ val θ ^ ( σ ) − val θ ( σ ) ∣ = ∣ ∑ s ∈ S ( θ ^ ( s ) − θ ( s ) ) g σ ( s ) ∣ ≤ δ < η 2 . \left|\operatorname{val}_{\widehat{\theta}}(\sigma)-\operatorname{val}_{\theta}(\sigma)\right|
=
\left|\sum_{s\in S}\left(\widehat{\theta}(s)-\theta(s)\right)g_{\sigma}(s)\right|
\leq\delta< \frac{\eta}{2}. val θ ( σ ) − val θ ( σ ) = s ∈ S ∑ ( θ ( s ) − θ ( s ) ) g σ ( s ) ≤ δ < 2 η . Taking maxima gives the same bound for their optima. The imported gap therefore yields optimum at least B − η B-\eta B − η A + η A+\eta A + η
Ordering constraints
An ordering CSP uses a global order of the input variables, rather than an assignment from a fixed finite domain. Fix an integer k ≥ 2 k\geq2 k ≥ 2 Π ⊂ S k \Pi\subset S_k Π ⊂ S k S k S_k S k { 1 , … , k } \{1,\ldots,k\} { 1 , … , k } [17 ] , we use an explicitly listed finite variable set V V V k k k ( v 1 , … , v k ) (v_1,\ldots,v_k) ( v 1 , … , v k ) ≺ \prec ≺
v π ( 1 ) ≺ ⋯ ≺ v π ( k ) v_{\pi(1)}\prec\cdots\prec v_{\pi(k)} v π ( 1 ) ≺ ⋯ ≺ v π ( k ) for some π ∈ Π \pi\in\Pi π ∈ Π
Write OPT Π ( I ) \operatorname{OPT}_{\Pi}(I) OPT Π ( I ) ρ Π = ∣ Π ∣ / k ! \rho_{\Pi}=|\Pi|/k! ρ Π = ∣Π∣/ k ! OPT Π ( I ) ≤ 1 \operatorname{OPT}_{\Pi}(I)\leq1 OPT Π ( I ) ≤ 1 ρ Π \rho_{\Pi} ρ Π k k k k ! k! k ! V V V
Corollary 8.2 (Ordering-CSP consequence). Fix k ≥ 2 k\geq2 k ≥ 2 ∅ ≠ Π ⊆ S k \varnothing\ne\Pi\subseteq S_k ∅ = Π ⊆ S k ρ Π = ∣ Π ∣ / k ! \rho_{\Pi}=|\Pi|/k! ρ Π = ∣Π∣/ k ! 0 < ϵ < ( 1 − ρ Π ) / 2 0<\epsilon<(1-\rho_{\Pi})/2 0 < ϵ < ( 1 − ρ Π ) /2 N P NP N P Π \Pi Π I I I
OPT Π ( I ) ≥ 1 − ϵ from those satisfying OPT Π ( I ) ≤ ρ Π + ϵ . \operatorname{OPT}_{\Pi}(I)\geq1-\epsilon
\qquad\text{from those satisfying}\qquad
\operatorname{OPT}_{\Pi}(I)\leq\rho_{\Pi}+\epsilon. OPT Π ( I ) ≥ 1 − ϵ from those satisfying OPT Π ( I ) ≤ ρ Π + ϵ . Consequently, approximation at every fixed ratio r ∈ ( ρ Π , 1 ] r\in(\rho_{\Pi},1] r ∈ ( ρ Π , 1 ] N P NP N P ρ Π \rho_{\Pi} ρ Π
Proof. Proposition A.2 constructs the stated finite instance from a simple strong-left Unique Games instance. It uses the local gap and analytic estimates of Guruswami et al. [17 ] and fixes the required game errors and degree conditions before the alphabet is chosen. Lemma A.1 supplies that game from Theorem 1.1; composing the reductions proves the displayed gap for the original predicate Π \Pi Π
For a fixed r ∈ ( ρ Π , 1 ] r \in(\rho_{\Pi},1] r ∈ ( ρ Π , 1 ] ε < ( r − ρ Π ) / ( 1 + r ) \varepsilon< (r-\rho_{\Pi})/(1+r) ε < ( r − ρ Π ) / ( 1 + r ) r ( 1 − ε ) > ρ Π + ε r(1-\varepsilon) > \rho_{\Pi}+\varepsilon r ( 1 − ε ) > ρ Π + ε r r r
For Maximum Acyclic Subgraph in the finite weighted directed-graph model, take k = 2 k=2 k = 2 Π = { 12 } \Pi=\{12\} Π = { 12 } ( u , v ) (u,v) ( u , v ) 1 / 2 1/2 1/2 ( a , b , c ) (a,b,c) ( a , b , c ) b b b a a a c c c Π = { 123 , 321 } ⊂ S 3 \Pi=\{123,321\}\subset S_3 Π = { 123 , 321 } ⊂ S 3 2 / 3 ! = 1 / 3 2/3!=1/3 2/3 ! = 1/3 [17 ] . These finite weighted consequences have near-perfect completeness with fixed positive error.
Cut, deletion, and clustering consequences
For the cut problems of Chawla, Krauthgamer, Kumar, Rabani, and Sivakumar [9 ] , let G = ( V , E ) G=(V,E) G = ( V , E ) c e c_e c e D = { { s i , t i } : 1 ≤ i ≤ k } D=\{\{s_i,t_i\}:1\le i\le k\} D = {{ s i , t i } : 1 ≤ i ≤ k } k ≥ 1 k\ge1 k ≥ 1 s i ≠ t i s_i\ne t_i s i = t i M ⊆ E M\subseteq E M ⊆ E c ( M ) = ∑ e ∈ M c e c(M)=\sum_{e\in M}c_e c ( M ) = ∑ e ∈ M c e q D ( M ) q_D(M) q D ( M ) G − M G-M G − M c ( M ) c(M) c ( M ) q D ( M ) = k q_D(M)=k q D ( M ) = k c ( M ) / q D ( M ) c(M)/q_D(M) c ( M ) / q D ( M ) M M M q D ( M ) > 0 q_D(M)>0 q D ( M ) > 0
For weighted Min-2CNF≡ Deletion, the input consists of clauses ( ℓ ≡ ℓ ′ ) (\ell\equiv\ell') ( ℓ ≡ ℓ ′ ) ℓ , ℓ ′ \ell,\ell' ℓ , ℓ ′
In the arbitrary weighted-graph form of Correlation Clustering, each present edge has a + + + − - − + + + − - − [10 ] .
Corollary 8.3 (Cut, deletion, and clustering hardness). For every fixed real constant C > 1 C>1 C > 1 C C C P = N P \mathrm{P}=\mathrm{NP} P = NP
Proof. Corollary 1.3 of [9 ] gives the first three conclusions under its ordinary edge-value Unique Games hypothesis. For a requested factor C C C L L L C C C L L L [ d ] [d] [ d ] d = 2 s ≥ 2 d=2^s\ge2 d = 2 s ≥ 2
For Correlation Clustering, the hard Multicut instances in [9 ] have distinct antipodal demand pairs inside d d d d ≥ 2 d\ge2 d ≥ 2 [10 ] ... and Corollary 4.8] therefore creates no opposite-signed parallel edges. It preserves the optimum and converts every clustering into a multicut of no greater cost, so the same fixed-factor hardness transfers.
The separate manuscript [33 ] proves NP-hardness at every fixed factor C > 1 C > 1 C > 1
Kernel clustering. A separate companion application concerns the following maximization problem. For identity-target kernel clustering , fix an integer k ≥ 3 k \ge3 k ≥ 3 A = ( a p q ) p , q = 1 N ⪰ 0 A = (a_{pq})_{p,q=1}^{N} \succeq0 A = ( a pq ) p , q = 1 N ⪰ 0 A 1 = 0 A\mathbf{1} = 0 A 1 = 0 1 \mathbf{1} 1 σ : { 1 , … , N } → { 1 , … , k } \sigma: \{1,\ldots,N\} \to\{1,\ldots,k\} σ : { 1 , … , N } → { 1 , … , k }
val A ( σ ) = ∑ p , q = 1 N a p q 1 { σ ( p ) = σ ( q ) } , OPT k ( A ) = max σ val A ( σ ) . \operatorname{val}_{A}(\sigma) = \sum_{p,q=1}^{N} a_{pq}\mathbf{1}_{\{\sigma(p)=\sigma(q)\}}, \qquad\operatorname{OPT}_{k}(A) = \max_{\sigma} \operatorname{val}_{A}(\sigma). val A ( σ ) = p , q = 1 ∑ N a pq 1 { σ ( p ) = σ ( q )} , OPT k ( A ) = σ max val A ( σ ) . The sum includes ordered pairs and the diagonal; empty clusters are allowed, and there is no normalization by cluster size. A loss factor α ≥ 1 \alpha\ge1 α ≥ 1 OPT k ( A ) / α \operatorname{OPT}_{k}(A)/\alpha OPT k ( A ) / α
1 ≤ α < α k , α k = 8 π 9 ( 1 − 1 k ) , 1 \le\alpha< \alpha_k, \qquad\alpha_k = \frac{8\pi}{9}\left(1-\frac{1}{k}\right), 1 ≤ α < α k , α k = 9 8 π ( 1 − k 1 ) , for each fixed k ≥ 3 k \ge3 k ≥ 3 [35 ] . This is strict hardness below the propeller rounding factor α k \alpha_k α k
Some of the reductions in Section 8 use a bipartite Unique Games instance in which a nearly satisfying labeling satisfies all constraints incident to most left vertices. We first obtain a simple graph with this property and with a prescribed lower bound on its common left degree. We then use it to give the finite rational formulation of the ordering consequence. The local ordering construction follows Guruswami, Håstad, Manokaran, Raghavendra, and Charikar [17 ] and uses the low-influence results cited below. The composition specifies the graph, the independent neighbor choices, and the conversion to constraints on distinct variables.
Orient the constraints of a bipartite game from its left side to its right side. A left vertex is strongly satisfied by a labeling when every edge incident to it is satisfied.
Lemma A.1 (Simple strong-left games). Fix 0 < ζ , ν < 1 0 < \zeta,\nu< 1 0 < ζ , ν < 1 d , H ≥ 1 d,H \ge1 d , H ≥ 1 h , R ≥ 1 h,R \ge1 h , R ≥ 1 h ≥ H h \ge H h ≥ H d ∣ h d \mid h d ∣ h Φ = ( A , B , E ) \Phi= (A,B,E) Φ = ( A , B , E ) [ R ] [R] [ R ] h h h Φ \Phi Φ 1 − ζ 1-\zeta 1 − ζ A A A Φ \Phi Φ val ( Φ ) < ν \operatorname{val}(\Phi) < \nu val ( Φ ) < ν h h h ζ , ν , d , H \zeta,\nu,d,H ζ , ν , d , H R R R Proof. We adapt the normalization and sequence construction of Khot and Regev [27 ] [Lemmas 3.3, 3.4, and 3.6]. The extra copies of right vertices used below ensure that the final graph is simple.
Choose a multiple h h h d d d
h ≥ max { H , 2 } , 1 h < ν 4 . h \ge\max\{H,2\}, \qquad\frac{1}{h} < \frac{\nu}{4}. h ≥ max { H , 2 } , h 1 < 4 ν . For ( T ) h = T ( T − 1 ) ⋯ ( T − h + 1 ) (T)_h = T(T-1)\cdots(T-h+1) ( T ) h = T ( T − 1 ) ⋯ ( T − h + 1 ) T ≥ h T \ge h T ≥ h
p g r a p h : = ( T ) h T h > 3 4 . p_{\mathrm{graph}} := \frac{(T)_h}{T^h} > \frac{3}{4}. p graph := T h ( T ) h > 4 3 . Such a choice exists because 1 − ( T ) h / T h ≤ ( h 2 ) / T 1-(T)_h/T^h \le\binom{h}{2}/T 1 − ( T ) h / T h ≤ ( 2 h ) / T β , γ , u \beta,\gamma,u β , γ , u L 2 L_2 L 2
β < ν 4 , h 2 γ < ν 4 , ( h + 1 ) u < ζ 2 , 1 L 2 < min { β γ 2 , ζ 2 h } . \beta< \frac{\nu}{4}, \qquad h^2\gamma< \frac{\nu}{4}, \qquad(h+1)u < \frac{\zeta}{2}, \qquad\frac{1}{L_2} < \min\left\{\frac{\beta\gamma}{2},\frac{\zeta}{2h}\right\}. β < 4 ν , h 2 γ < 4 ν , ( h + 1 ) u < 2 ζ , L 2 1 < min { 2 β γ , 2 h ζ } . Finally choose positive rational γ 0 , ζ 0 < 1 / 2 \gamma_0,\zeta_0 < 1/2 γ 0 , ζ 0 < 1/2
2 γ 0 < β γ 2 , 2 ζ 0 < u . 2\gamma_0 < \frac{\beta\gamma}{2}, \qquad\sqrt{2\zeta_0} < u. 2 γ 0 < 2 β γ , 2 ζ 0 < u . All these choices precede the invocation of Theorem 1.1 with completeness error ζ 0 \zeta_0 ζ 0 γ 0 \gamma_0 γ 0
Write its output as Φ 0 = ( X 0 , Y , E 0 ) \Phi_0=(X_0,Y,E_0) Φ 0 = ( X 0 , Y , E 0 ) [ R ] [R] [ R ] M 0 = ∣ E 0 ∣ > 0 M_0=|E_0|>0 M 0 = ∣ E 0 ∣ > 0 1 / M 0 1/M_0 1/ M 0 w x w_x w x x x x
n x = ⌊ 2 ∣ X 0 ∣ w x ⌋ n_x=\lfloor2|X_0|w_x\rfloor n x = ⌊ 2∣ X 0 ∣ w x ⌋ copies of x x x w x y / w x w_{xy}/w_x w x y / w x w x > 0 w_x>0 w x > 0 X 1 X_1 X 1
∣ X 0 ∣ ≤ ∣ X 1 ∣ = ∑ x n x ≤ 2 ∣ X 0 ∣ , |X_0| \le|X_1|=\sum_x n_x \le2|X_0|, ∣ X 0 ∣ ≤ ∣ X 1 ∣ = x ∑ n x ≤ 2∣ X 0 ∣ , and the incident weight at each copy is one.
Here and below a local satisfied weight uses the labels at that left vertex and at the shared right vertices. Given any labeling of the copy game, keep the right labels and give all copies of each x x x L L L Φ 0 \Phi_0 Φ 0
∑ x ′ ∈ X 1 w s a t ( x ′ ) ≤ ∑ x : n x > 0 n x w x w s a t , L ( x ) ≤ 2 ∣ X 0 ∣ w s a t , L ( Φ 0 ) . \sum_{x'\in X_1} w_{\mathrm{sat}}(x') \le\sum_{x:n_x>0}\frac{n_x}{w_x}w_{\mathrm{sat},L}(x) \le2|X_0|w_{\mathrm{sat},L}(\Phi_0). x ′ ∈ X 1 ∑ w sat ( x ′ ) ≤ x : n x > 0 ∑ w x n x w sat , L ( x ) ≤ 2∣ X 0 ∣ w sat , L ( Φ 0 ) . Consequently the copy game’s normalized value is at most 2 γ 0 2\gamma_0 2 γ 0 Φ 0 \Phi_0 Φ 0 ζ 0 \zeta_0 ζ 0 2 ζ 0 < u 2 2\zeta_0<u^2 2 ζ 0 < u 2 1 − u 1-u 1 − u X 1 X_1 X 1 1 − u 1-u 1 − u
To remove the weights, put α = L 2 ∣ Y ∣ \alpha=L_2|Y| α = L 2 ∣ Y ∣ x ∈ X 1 x\in X_1 x ∈ X 1 w ~ x y \widetilde w_{xy} w x y y 0 y_0 y 0 α w ~ x y \alpha\widetilde w_{xy} α w x y y ≠ y 0 y\ne y_0 y = y 0 y 0 y_0 y 0 Φ o c c \Phi_{\mathrm{occ}} Φ occ α \alpha α ∣ Y ∣ / α = 1 / L 2 |Y|/\alpha=1/L_2 ∣ Y ∣/ α = 1/ L 2 y 0 y_0 y 0
val ( Φ o c c ) ≤ 2 2 γ 0 + 1 L 2 < β γ on a NO input. (43) \operatorname{val}(\Phi_{\mathrm{occ}}) \le2^{2}\gamma_0 + \frac{1}{L_2} < \beta\gamma\quad\text{on a NO input.} \tag*{(43)} val ( Φ occ ) ≤ 2 2 γ 0 + L 2 1 < β γ on a NO input. (43) On a YES input, the labeling above has satisfied occurrence fraction at least 1 − a 1-a 1 − a a = u + 1 / L 2 a=u+1/L_2 a = u + 1/ L 2 1 − u 1-u 1 − u X 1 X_1 X 1
Index the α \alpha α x x x j j j y j y_j y j π j \pi_j π j y ∈ Y y \in Y y ∈ Y ( y , t ) (y,t) ( y , t ) t ∈ [ T ] t \in[T] t ∈ [ T ] j j j T T T x x x ( y j , t ) (y_j,t) ( y j , t ) π j \pi_j π j α T \alpha T α T Φ t a g \Phi_{\mathrm{tag}} Φ tag Φ t a g \Phi_{\mathrm{tag}} Φ tag y y y y y y ( y , t ) (y,t) ( y , t ) Φ o c c \Phi_{\mathrm{occ}} Φ occ Φ t a g \Phi_{\mathrm{tag}} Φ tag
val ( Φ t a g ) ≤ val ( Φ o c c ) < β γ on a NO input. (44) \operatorname{val}(\Phi_{\mathrm{tag}}) \le\operatorname{val}(\Phi_{\mathrm{occ}}) < \beta\gamma\quad\text{on a NO input.} \tag*{(44)} val ( Φ tag ) ≤ val ( Φ occ ) < β γ on a NO input. (44) The tag-independent lift of the YES labeling preserves every local satisfied fraction.
Consider the full sequence graph whose left vertices are
( x , ( j 1 , t 1 ) , … , ( j h , t h ) ) , j i ∈ [ α ] , t i ∈ [ T ] , (x,(j_1,t_1),\ldots,(j_h,t_h)), \qquad j_i \in[\alpha], \quad t_i \in[T], ( x , ( j 1 , t 1 ) , … , ( j h , t h )) , j i ∈ [ α ] , t i ∈ [ T ] , with position i i i ( y j i , t i ) (y_{j_i},t_i) ( y j i , t i ) π j i \pi_{j_i} π j i x x x ( α T ) h (\alpha T)^h ( α T ) h h h h x x x h h h x x x
Fix arbitrary right labels in Φ t a g \Phi_{\mathrm{tag}} Φ tag x x x p x ( ℓ ) p_x(\ell) p x ( ℓ ) ℓ \ell ℓ p x ( ℓ ) p_x(\ell) p x ( ℓ ) x x x
E x max ℓ p x ( ℓ ) ≤ val ( Φ t a g ) < β γ . \mathop{\mathbb{E}}_x \max_{\ell} p_x(\ell) \le\operatorname{val}(\Phi_{\mathrm{tag}}) < \beta\gamma. E x ℓ max p x ( ℓ ) ≤ val ( Φ tag ) < β γ . Fewer than a β \beta β x x x max ℓ p x ( ℓ ) ≥ γ \max_{\ell} p_x(\ell) \ge\gamma max ℓ p x ( ℓ ) ≥ γ x x x h h h
( h 2 ) ∑ ℓ p x ( ℓ ) 2 ≤ ( h 2 ) max ℓ p x ( ℓ ) < h 2 γ . \binom{h}{2}\sum_{\ell}p_x(\ell)^2 \le\binom{h}{2}\max_{\ell}p_x(\ell) < h^2\gamma. ( 2 h ) ℓ ∑ p x ( ℓ ) 2 ≤ ( 2 h ) ℓ max p x ( ℓ ) < h 2 γ . If no two determined labels agree, any label of the sequence vertex satisfies at most one of its h h h x x x 1 / h + h 2 γ < 1 1/h+h^2\gamma<1 1/ h + h 2 γ < 1
s : = β + 1 h + ( 1 − β ) h 2 γ < 3 ν 4 . (45) s := \beta+\frac{1}{h}+(1-\beta)h^2\gamma< \frac{3\nu}{4}. \tag*{(45)} s := β + h 1 + ( 1 − β ) h 2 γ < 4 3 ν . (45) The estimate holds for every choice of the right labels and every sequence-dependent choice of left labels.
Retain only sequence vertices for which t 1 , … , t h t_1,\ldots,t_h t 1 , … , t h x x x ( j 1 , … , j h ) (j_1,\ldots,j_h) ( j 1 , … , j h ) ( T ) h (T)_h ( T ) h x x x α h ( T ) h \alpha^h(T)_h α h ( T ) h p g r a p h p_{\mathrm{graph}} p graph h h h h h h
Give each sequence vertex based at x x x x x x i i i j i j_i j i x x x Φ o c c \Phi_{\mathrm{occ}} Φ occ f x f_x f x f x h f_x^h f x h x x x
( 1 − u ) ( 1 − a ) h ≥ 1 − u − h a = 1 − ( h + 1 ) u − h L 2 > 1 − ζ . (1-u)(1-a)^h \ge1-u-ha = 1-(h+1)u-\frac{h}{L_2} > 1-\zeta. ( 1 − u ) ( 1 − a ) h ≥ 1 − u − ha = 1 − ( h + 1 ) u − L 2 h > 1 − ζ . Here 0 < a < 1 0<a<1 0 < a < 1
For NO, extend any labeling of the retained graph to the full graph by giving discarded left vertices arbitrary labels and keeping all right labels. All left degrees are h h h p g r a p h p_{\mathrm{graph}} p graph (45) , the latter is at most
s p g r a p h < 3 ν / 4 3 / 4 = ν . \frac{s}{p_{\mathrm{graph}}}<\frac{3\nu/4}{3/4}=\nu. p graph s < 3/4 3 ν /4 = ν . This extension permits arbitrary dependence of the retained left labels on their tags.
All the operations are finite and deterministic. If N N N Φ 0 \Phi_0 Φ 0 ∣ X 1 ∣ = O ( N ) |X_1|=O(N) ∣ X 1 ∣ = O ( N ) α = L 2 ∣ Y ∣ = O ( N ) \alpha=L_2|Y|=O(N) α = L 2 ∣ Y ∣ = O ( N ) ∣ X 1 ∣ α h ( T ) = O ( N h + 1 ) |X_1|\alpha^{(T)}_h=O(N^{h+1}) ∣ X 1 ∣ α h ( T ) = O ( N h + 1 ) h h h Φ 0 \Phi_0 Φ 0
The finite ordering transfer
The ordering theorem of Guruswami et al. uses a multiscale local instance and a low-influence rounding estimate. Their general outer composition is described as analogous to the two-query construction in their Section 7. The following proposition gives the composition for the rational occurrence-list model of Section 8. It separates the constants chosen for the ordering gap from the subsequently chosen Unique Games alphabet.
Proposition A.2 (Finite ordering transfer). Fix k ≥ 2 k\ge2 k ≥ 2 ∅ ≠ Π ⊊ S k \varnothing\ne\Pi\subsetneq S_k ∅ = Π ⊊ S k ρ Π = ∣ Π ∣ / k ! \rho_\Pi=|\Pi|/k! ρ Π = ∣Π∣/ k ! 0 < δ < ( 1 − ρ Π ) / 2 0<\delta<(1-\rho_\Pi)/2 0 < δ < ( 1 − ρ Π ) /2 q , H ≥ 1 q,H\ge1 q , H ≥ 1 ζ , ν < 1 \zeta,\nu<1 ζ , ν < 1 k , Π , δ k,\Pi,\delta k , Π , δ R ≥ 1 R\ge1 R ≥ 1
Let Φ = ( A , B , E ) \Phi=(A,B,E) Φ = ( A , B , E ) [ R ] [R] [ R ] A A A B B B h h h h ≥ H h\ge H h ≥ H q ∣ h q\mid h q ∣ h Φ \Phi Φ R R R Π \Pi Π ( 1 − ζ ) ∣ A ∣ (1-\zeta)|A| ( 1 − ζ ) ∣ A ∣ OPT Π ( I ) ≥ 1 − δ \operatorname{OPT}_{\Pi}(I)\ge1-\delta OPT Π ( I ) ≥ 1 − δ val ( Φ ) ≤ ν \operatorname{val}(\Phi)\le\nu val ( Φ ) ≤ ν OPT Π ( I ) ≤ ρ Π + δ \operatorname{OPT}_{\Pi}(I)\le\rho_\Pi+\delta OPT Π ( I ) ≤ ρ Π + δ q , H , ζ , ν q,H,\zeta,\nu q , H , ζ , ν R R R h h h
The output variables will be ( b , z ) ∈ B × [ m ] R (b,z)\in B\times[m]^R ( b , z ) ∈ B × [ m ] R [ m ] [m] [ m ] a ∈ A a\in A a ∈ A N ( a ) × [ m ] R N(a)\times[m]^R N ( a ) × [ m ] R q q q z z z z z z 1 / q 1/q 1/ q z z z a a a
For P = 1 Π P = 1_{\Pi} P = 1 Π π 0 ∈ Π \pi_0 \in\Pi π 0 ∈ Π
P 0 ( σ ) = P ( π 0 ∘ σ ) , σ ∈ S k . P_0(\sigma) = P(\pi_0 \circ\sigma), \qquad\sigma\in S_k. P 0 ( σ ) = P ( π 0 ∘ σ ) , σ ∈ S k . Then P 0 ( id ) = 1 P_0(\operatorname{id}) = 1 P 0 ( id ) = 1 ρ Π \rho_{\Pi} ρ Π r = ( r 1 , … , r k ) r = (r_1,\ldots,r_k) r = ( r 1 , … , r k ) Ref ( r ) \operatorname{Ref}(r) Ref ( r )
P ‾ 0 ( r ) = 1 ∣ Ref ( r ) ∣ ∑ σ ∈ Ref ( r ) P 0 ( σ ) . (46) \overline{P}_0(r) = \frac{1}{\lvert\operatorname{Ref}(r)\rvert}\sum_{\sigma\in\operatorname{Ref}(r)}P_0(\sigma). \tag*{(46)} P 0 ( r ) = ∣ Ref ( r )∣ 1 σ ∈ Ref ( r ) ∑ P 0 ( σ ) . (46) This is the uniform tie extension used in [17 ] , Section 8.2. It lies in [ 0 , 1 ] [0,1] [ 0 , 1 ] P 0 P_0 P 0
The normalization preserves the predicate after one permutation of tuple positions. Given a raw tuple w = ( w 1 , … , w k ) w=(w_1,\ldots,w_k) w = ( w 1 , … , w k ) v v v
v π 0 ( j ) = w j ( j ∈ [ k ] ) . (47) v_{\pi_0(j)} = w_j \qquad(j \in[k]). \tag*{(47)} v π 0 ( j ) = w j ( j ∈ [ k ]) . (47) If a strict order induces σ \sigma σ w w w π 0 ∘ σ \pi_0\circ\sigma π 0 ∘ σ v v v
Ref ( f ( v 1 ) , … , f ( v k ) ) = { π 0 ∘ σ : σ ∈ Ref ( f ( w 1 ) , … , f ( w k ) ) } . \operatorname{Ref}(f(v_1),\ldots,f(v_k))=\{\pi_0\circ\sigma:\sigma\in\operatorname{Ref}(f(w_1),\ldots,f(w_k))\}. Ref ( f ( v 1 ) , … , f ( v k )) = { π 0 ∘ σ : σ ∈ Ref ( f ( w 1 ) , … , f ( w k ))} . for every rank map f f f P P P P 0 P_0 P 0 (47) preserves distinctness and weights.
For a finite local instance J = ( U , C , ω ) J=(U,\mathcal{C},\omega) J = ( U , C , ω ) t c = ( u c , 1 , … , u c , k ) t_c=(u_{c,1},\ldots,u_{c,k}) t c = ( u c , 1 , … , u c , k ) c ∈ C c\in\mathcal{C} c ∈ C ω c \omega_c ω c q q q
opt q ( J ) = max g : U → [ q ] ∑ c ∈ C ω c P ‾ 0 ( g ( u c , 1 ) , … , g ( u c , k ) ) . \operatorname{opt}_q(J)=\max_{g:U\to[q]}\sum_{c\in\mathcal{C}}\omega_c\overline{P}_0(g(u_{c,1}),\ldots,g(u_{c,k})). opt q ( J ) = g : U → [ q ] max c ∈ C ∑ ω c P 0 ( g ( u c , 1 ) , … , g ( u c , k )) . Lemma A.3 (Rational local ordering data). For every integer q ≥ 1 q\geq1 q ≥ 1 η > 0 \eta>0 η > 0 J = ( U , C , ω ) J=(U,\mathcal{C},\omega) J = ( U , C , ω ) ∣ U ∣ = m ≥ 2 \lvert U\rvert=m\geq2 ∣ U ∣ = m ≥ 2 μ c \mu_c μ c [ m ] k [m]^k [ m ] k c c c k k k ω c \omega_c ω c μ c \mu_c μ c μ c \mu_c μ c [ m ] [m] [ m ] 0 < α ≤ 1 / 2 0<\alpha\leq1/2 0 < α ≤ 1/2 μ c ( x ) > α \mu_c(x)>\alpha μ c ( x ) > α c , x c,x c , x
opt q ( J ) ≤ ρ Π + η , v l o c : = ∑ c ω c E X ∼ μ c P ‾ 0 ( X ) ≥ 1 − η . (48) \operatorname{opt}_q(J)\leq\rho_{\Pi}+\eta,\qquad v_{\mathrm{loc}}:=\sum_c\omega_c\mathbb{E}_{X\sim\mu_c}\overline{P}_0(X)\geq1-\eta. \tag*{(48)} opt q ( J ) ≤ ρ Π + η , v loc := c ∑ ω c E X ∼ μ c P 0 ( X ) ≥ 1 − η . (48) The local laws have common feasible Gram data for the relaxation in [17 ] , Section 8.3: there are a unit vector I I I b u , j b_{u,j} b u , j u ∈ U u\in U u ∈ U j ∈ [ m ] j\in[m] j ∈ [ m ]
∑ j b u , j = I , ⟨ b u , i , b u , j ⟩ = 0 ( i ≠ j ) , ∥ b u , j ∥ 2 = 1 m , \sum_j b_{u,j}=I,\qquad\langle b_{u,i},b_{u,j}\rangle=0\ (i\ne j),\qquad\lVert b_{u,j}\rVert^2=\frac{1}{m}, j ∑ b u , j = I , ⟨ b u , i , b u , j ⟩ = 0 ( i = j ) , ∥ b u , j ∥ 2 = m 1 , and, for every two positions r , s r,s r , s c c c
⟨ b u c , r , i , b u c , s , j ⟩ = Pr X ∼ μ c [ X r = i , X s = j ] . (49) \langle b_{u_{c,r},i},b_{u_{c,s},j}\rangle=\Pr_{X\sim\mu_c}[X_r=i,X_s=j]. \tag*{(49)} ⟨ b u c , r , i , b u c , s , j ⟩ = X ∼ μ c Pr [ X r = i , X s = j ] . (49) All these data are fixed by $k,\Pi,q,\eta.
Proof. The explicit increasing-tuple construction in [17 ] , Theorem 11.1, Definition 11.2, and the proof of Theorem 2.5), applied to P 0 P_0 P 0 J ∗ J^* J ∗ opt q ( J ∗ ) ≤ ρ Π + η \operatorname{opt}_q(J^*) \le\rho_\Pi+\eta opt q ( J ∗ ) ≤ ρ Π + η
Use the finite-copy smoothing from the proof of [17 ] , Lemma 8.9), specialized to this complete order. Take L L L J ∗ J^* J ∗ 1 / L 1/L 1/ L σ : U → [ m ] \sigma:U\to[m] σ : U → [ m ] m = L ∣ U ∗ ∣ m=L|U^*| m = L ∣ U ∗ ∣ J J J opt q ( J ) ≤ ρ Π + η \operatorname{opt}_q(J)\le\rho_\Pi+\eta opt q ( J ) ≤ ρ Π + η q q q L L L s 0 < 1 s_0<1 s 0 < 1 1 / L + s 0 < η 1/L+s_0<\eta 1/ L + s 0 < η X : U → [ m ] X:U\to[m] X : U → [ m ] 1 − s 0 1-s_0 1 − s 0 σ \sigma σ s 0 s_0 s 0 [ m ] [m] [ m ]
Each variable is uniform in either part of the mixture. A cyclic cut can split at most one of the L L L 1 − 1 / L 1-1/L 1 − 1/ L ( 1 − s 0 ) ( 1 − 1 / L ) > 1 − η (1-s_0)(1-1/L)>1-\eta ( 1 − s 0 ) ( 1 − 1/ L ) > 1 − η μ c \mu_c μ c c c c n c ( x ) n_c(x) n c ( x ) m m m x x x
μ c ( x ) = ( 1 − s 0 ) n c ( x ) m + s 0 m k . \mu_c(x)=(1-s_0)\frac{n_c(x)}{m}+\frac{s_0}{m^k}. μ c ( x ) = ( 1 − s 0 ) m n c ( x ) + m k s 0 . These atoms are rational and exceed α : = s 0 / ( 2 m k ) \alpha:=s_0/(2m^k) α := s 0 / ( 2 m k ) m k m^k m k c c c
Finally regard the finite mixture as a probability space and take I = 1 I=1 I = 1 b u , j = 1 { X ( u ) = j } b_{u,j}=\mathbf{1}_{\{X(u)=j\}} b u , j = 1 { X ( u ) = j } L 2 L^2 L 2 c c c
For scalar functions on the uniform product [ m ] R [m]^R [ m ] R
Inf ℓ ( F ) = E [ Var z ℓ ( F ∣ z − ℓ ) ] . \operatorname{Inf}_{\ell}(F)=\mathbb{E}[\operatorname{Var}_{z_\ell}(F\mid z_{-\ell})]. Inf ℓ ( F ) = E [ Var z ℓ ( F ∣ z − ℓ )] . The noise operator T θ T_\theta T θ 0 ≤ θ ≤ 1 0\le\theta\le1 0 ≤ θ ≤ 1 θ \theta θ
T θ F = ∑ σ θ ∣ σ ∣ F ^ ( σ ) χ σ , Inf ℓ ( F ) = ∑ σ : σ ℓ ≠ 0 F ^ ( σ ) 2 . (50) T_\theta F=\sum_{\sigma}\theta^{|\sigma|}\widehat{F}(\sigma)\chi_\sigma,\qquad\operatorname{Inf}_{\ell}(F)=\sum_{\sigma:\sigma_\ell\ne0}\widehat{F}(\sigma)^2. \tag*{(50)} T θ F = σ ∑ θ ∣ σ ∣ F ( σ ) χ σ , Inf ℓ ( F ) = σ : σ ℓ = 0 ∑ F ( σ ) 2 . (50) In particular, further smoothing decreases every influence.
Lemma A.4 (Uniform collision estimate). For every 0 < κ < 1 / 2 0<\kappa<1/2 0 < κ < 1/2 there is μ 0 ( κ ) > 0 \mu_0(\kappa)>0 μ 0 ( κ ) > 0 For each m ≥ 2 m\ge2 m ≥ 2 there is a nonnegative function r c m , κ ( t ) → 0 r_c^{m,\kappa}(t)\to0 r c m , κ ( t ) → 0 as t ↓ 0 t\downarrow0 t ↓ 0 with the following property, uniformly over all R ≥ 1 R\ge1 R ≥ 1 Let F , G : [ m ] R → [ 0 , 1 ] F,G:[m]^R\to[0,1] F , G : [ m ] R → [ 0 , 1 ] have the same mean 0 < μ ≤ μ 0 ( κ ) 0<\mu\le\mu_0(\kappa) 0 < μ ≤ μ 0 ( κ ) and satisfy
Inf ℓ ( T 1 − κ F ) ≤ t , Inf ℓ ( T 1 − κ G ) ≤ t ( ℓ ∈ [ R ] ) . \operatorname{Inf}_{\ell}(T_{1-\kappa}F)\le t,\qquad\operatorname{Inf}_{\ell}(T_{1-\kappa}G)\le t\qquad(\ell\in[R]). Inf ℓ ( T 1 − κ F ) ≤ t , Inf ℓ ( T 1 − κ G ) ≤ t ( ℓ ∈ [ R ]) . For every coupling ( Z , Z ′ ) (Z,Z') ( Z , Z ′ ) whose two marginals are uniform on [ m ] R [m]^R [ m ] R
E [ ( T 1 − 2 κ F ) ( Z ) ( T 1 − 2 κ G ) ( Z ′ ) ] ≤ μ 1 + κ / 2 + r c m , κ ( t ) . (51) \mathbb{E}\big[(T_{1-2\kappa}F)(Z)(T_{1-2\kappa}G)(Z')\big]\le\mu^{1+\kappa/2}+r_c^{m,\kappa}(t). \tag*{(51)} E [ ( T 1 − 2 κ F ) ( Z ) ( T 1 − 2 κ G ) ( Z ′ ) ] ≤ μ 1 + κ /2 + r c m , κ ( t ) . (51) The function r c m , κ r_c^{m,\kappa} r c m , κ is independent of R , μ , F , G R,\mu,F,G R , μ , F , G and the coupling.
Proof. This is the dimension-uniform form of [17 ] , Lemmas 3.4 and 3.5 needed here. For H = T 1 − κ F H=T_{1-\kappa}F H = T 1 − κ F
∥ T 1 − 2 κ F ∥ 2 2 ≤ Stab 1 − κ ( H ) , \lVert T_{1-2\kappa}F\rVert_2^2 \le\operatorname{Stab}_{1-\kappa}(H), ∥ T 1 − 2 κ F ∥ 2 2 ≤ Stab 1 − κ ( H ) , where Stab θ ( H ) = ∑ σ θ ∣ σ ∣ H ^ ( σ ) 2 \operatorname{Stab}_{\theta}(H)=\sum_{\sigma}\theta^{|\sigma|}\widehat{H}(\sigma)^2 Stab θ ( H ) = ∑ σ θ ∣ σ ∣ H ( σ ) 2 ( 1 − κ ) 3 − ( 1 − 2 κ ) 2 = κ ( 1 − κ − κ 2 ) > 0 (1-\kappa)^3-(1-2\kappa)^2=\kappa(1-\kappa-\kappa^2)>0 ( 1 − κ ) 3 − ( 1 − 2 κ ) 2 = κ ( 1 − κ − κ 2 ) > 0 H H H [32 ] . Apply that theorem with product dimension R R R 1 / m 1/m 1/ m 1 − κ 1-\kappa 1 − κ t t t
Stab 1 − κ ( H ) ≤ Γ 1 − κ ( μ ) + C log ( 2 m ) κ log log ( 1 / t ) log ( 1 / t ) . \operatorname{Stab}_{1-\kappa}(H)\le\Gamma_{1-\kappa}(\mu)+C\frac{\log(2m)}{\kappa}\frac{\log\log(1/t)}{\log(1/t)}. Stab 1 − κ ( H ) ≤ Γ 1 − κ ( μ ) + C κ log ( 2 m ) log ( 1/ t ) log log ( 1/ t ) . The cutoff and this error are independent of R R R μ \mu μ Γ θ ( μ ) \Gamma_{\theta}(\mu) Γ θ ( μ ) μ \mu μ
For fixed κ \kappa κ Γ 1 − κ ( μ ) = μ 2 / ( 2 − κ ) + o ( 1 ) \Gamma_{1-\kappa}(\mu)=\mu^{2/(2-\kappa)+o(1)} Γ 1 − κ ( μ ) = μ 2/ ( 2 − κ ) + o ( 1 ) μ ↓ 0 \mu\downarrow0 μ ↓ 0
2 2 − κ − ( 1 + κ 2 ) = κ 2 2 ( 2 − κ ) > 0 , \frac{2}{2-\kappa}-\left(1+\frac{\kappa}{2}\right)=\frac{\kappa^2}{2(2-\kappa)}>0, 2 − κ 2 − ( 1 + 2 κ ) = 2 ( 2 − κ ) κ 2 > 0 , there is a cutoff μ 0 ( κ ) > 0 \mu_0(\kappa)>0 μ 0 ( κ ) > 0 m , R m,R m , R Γ 1 − κ ( μ ) ≤ μ 1 + κ / 2 \Gamma_{1-\kappa}(\mu)\le\mu^{1+\kappa/2} Γ 1 − κ ( μ ) ≤ μ 1 + κ /2 L 2 L^2 L 2 F F F G G G r c m , κ ( t ) → 0 r_c^{m,\kappa}(t)\to0 r c m , κ ( t ) → 0 t 0 < e − e t_0<e^{-e} t 0 < e − e 0 < t < t 0 0<t<t_0 0 < t < t 0 r c m , κ ( t ) = 1 r_c^{m,\kappa}(t)=1 r c m , κ ( t ) = 1 t ≥ t 0 t\ge t_0 t ≥ t 0 (51) .
Write S q = { p ∈ [ 0 , 1 ] q : ∑ j p j = 1 } S_q=\{p\in[0,1]^q:\sum_jp_j=1\} S q = { p ∈ [ 0 , 1 ] q : ∑ j p j = 1 } P ‾ 0 \overline{P}_0 P 0 [ q ] k [q]^k [ q ] k
P 0 m l ( p 1 , … , p k ) = ∑ r ∈ [ q ] k P ‾ 0 ( r ) ∏ i = 1 k p i r i , p i ∈ S q . (52) P_0^{\mathrm{ml}}(p_1,\ldots,p_k)=\sum_{r\in[q]^k}\overline{P}_0(r)\prod_{i=1}^{k}p_i^{r_i},\qquad p_i\in S_q. \tag*{(52)} P 0 ml ( p 1 , … , p k ) = r ∈ [ q ] k ∑ P 0 ( r ) i = 1 ∏ k p i r i , p i ∈ S q . (52) Lemma A.5 (A simplex-valued local estimate). Let J , μ c , α J,\mu_c,\alpha J , μ c , α 0 < λ < 1 0<\lambda<1 0 < λ < 1 R ≥ 1 R\ge1 R ≥ 1 c c c ω c \omega_c ω c c c c R R R μ c \mu_c μ c Z 1 , … , Z k ∈ [ m ] R Z_1,\ldots,Z_k\in[m]^R Z 1 , … , Z k ∈ [ m ] R Z ~ i \widetilde{Z}_i Z i λ \lambda λ F = ( F 1 , … , F q ) : [ m ] R → S q F=(F^1,\ldots,F^q):[m]^R\to S_q F = ( F 1 , … , F q ) : [ m ] R → S q c c c 0 < t < 1 / ( k q ) 0<t<1/(kq) 0 < t < 1/ ( k q )
Inf ℓ ( T 1 − λ F j ) ≤ t ( ℓ ∈ [ R ] , j ∈ [ q ] ) . \operatorname{Inf}_{\ell}(T_{1-\lambda}F^j)\le t\qquad(\ell\in[R],\ j\in[q]). Inf ℓ ( T 1 − λ F j ) ≤ t ( ℓ ∈ [ R ] , j ∈ [ q ]) . Then
E c , Z , Z ~ P 0 m l ( F ( Z ~ 1 ) , … , F ( Z ~ k ) ) ≤ opt q ( J ) + r s ( k q t ) , (53) \mathbb{E}_{c,Z,\widetilde{Z}}P_0^{\mathrm{ml}}\bigl(F(\widetilde{Z}_1),\ldots,F(\widetilde{Z}_k)\bigr)\le\operatorname{opt}_q(J)+r_s(kqt), \tag*{(53)} E c , Z , Z P 0 ml ( F ( Z 1 ) , … , F ( Z k ) ) ≤ opt q ( J ) + r s ( k q t ) , (53) where r s ( u ) → 0 r_s(u)\to0 r s ( u ) → 0 u ↓ 0 u\downarrow0 u ↓ 0 R R R r s r_s r s k , q , λ k,q,\lambda k , q , λ
Proof. This is the simplex-valued estimate of [17 ] , Lemma 10.5, with its sufficient scalar influence bounds and their dependence made explicit. Put H = T 1 − λ F H=T_{1-\lambda}F H = T 1 − λ F (53) into
E c E Z ∼ μ c R P 0 m l ( H ( Z 1 ) , … , H ( Z k ) ) . (54) \mathbb{E}_{c}\mathbb{E}_{Z\sim\mu_c^R}P_0^{\mathrm{ml}}\bigl(H(Z_1),\ldots,H(Z_k)\bigr). \tag*{(54)} E c E Z ∼ μ c R P 0 ml ( H ( Z 1 ) , … , H ( Z k ) ) . (54) For each coordinate, the integral ensemble consists of the indicators 1 { X i = j } 1\{X_i=j\} 1 { X i = j } μ c \mu_c μ c α \alpha α (49) supply one Gaussian ensemble for all variables of J J J [17 ] (Lemma 10.4). Explicitly, for a standard Gaussian vector g g g
G u , j = ⟨ I , b u , j ⟩ + ⟨ b u , j − ⟨ I , b u , j ⟩ I , g ⟩ G_{u,j}=\langle I,b_{u,j}\rangle+\langle b_{u,j}-\langle I,b_{u,j}\rangle I,g\rangle G u , j = ⟨ I , b u , j ⟩ + ⟨ b u , j − ⟨ I , b u , j ⟩ I , g ⟩ have those moments. Use independent copies of this ensemble in the R R R H j H^j H j [ m ] [m] [ m ]
For a fixed c c c T θ c T_\theta^c T θ c θ \theta θ μ c \mu_c μ c
T 1 − λ c [ F j ( Z i ) ] = ( T 1 − λ F j ) ( Z i ) = H j ( Z i ) . T_{1-\lambda}^c[F^j(Z_i)]=(T_{1-\lambda}F^j)(Z_i)=H^j(Z_i). T 1 − λ c [ F j ( Z i )] = ( T 1 − λ F j ) ( Z i ) = H j ( Z i ) . Thus these are the smoothed components required by the invariance theorem on the product of the tuple ensembles. The same marginals give the exact influence identity below; the superscript indicates the product measure used to compute influence:
Inf ℓ μ c ⊗ R ( H j ( Z i ) ) = Inf ℓ [ m ] R ( H j ) . (55) \operatorname{Inf}_{\ell}^{\mu_c^{\otimes R}}(H^j(Z_i))=\operatorname{Inf}_{\ell}^{[m]^R}(H^j). \tag*{(55)} Inf ℓ μ c ⊗ R ( H j ( Z i )) = Inf ℓ [ m ] R ( H j ) . (55) Indeed, conditioning on every coordinate tuple except the ℓ \ell ℓ ℓ \ell ℓ i i i [21 ] (Definition 2.6). Thus the vector ( H j ( Z i ) ) i ∈ [ k ] , j ∈ [ q ] (H^j(Z_i))_{i\in[k],j\in[q]} ( H j ( Z i ) ) i ∈ [ k ] , j ∈ [ q ] k q t kqt k q t
For the remaining tail hypothesis, let ( F j ( Z i ) ) S (F^j(Z_i))_S ( F j ( Z i ) ) S S ⊆ [ R ] S\subseteq[R] S ⊆ [ R ] μ c ⊗ R \mu_c^{\otimes R} μ c ⊗ R > d >d > d ∣ S ∣ > d |S|>d ∣ S ∣ > d S S S ( 1 − λ ) ∣ S ∣ (1-\lambda)^{|S|} ( 1 − λ ) ∣ S ∣ F j F^j F j [ 0 , 1 ] [0,1] [ 0 , 1 ] d > 0 d>0 d > 0
Var ( ( H j ( Z i ) ) > d ) = ∑ ∣ S ∣ > d ( 1 − λ ) 2 ∣ S ∣ ∥ ( F j ( Z i ) ) S ∥ 2 2 ≤ ( 1 − λ ) 2 d Var ( F j ( Z i ) ) ≤ ( 1 − λ ) 2 d . \operatorname{Var}((H^j(Z_i))^{>d})=\sum_{|S|>d}(1-\lambda)^{2|S|}\lVert(F^j(Z_i))_S\rVert_2^2
\le(1-\lambda)^{2d}\operatorname{Var}(F^j(Z_i))\le(1-\lambda)^{2d}. Var (( H j ( Z i ) ) > d ) = ∣ S ∣ > d ∑ ( 1 − λ ) 2∣ S ∣ ∥( F j ( Z i ) ) S ∥ 2 2 ≤ ( 1 − λ ) 2 d Var ( F j ( Z i )) ≤ ( 1 − λ ) 2 d . All norms and variances here use μ c ⊗ R \mu_c^{\otimes R} μ c ⊗ R [21 ] (Theorem 3.6). These are sufficient hypotheses for the vector-valued invariance estimate stated in [17 ] (Theorem 10.1).
Let p : R q → S q p:\mathbb{R}^q\to S_q p : R q → S q
Ψ ( x 1 , … , x k ) = P 0 m l ( p ( x 1 ) , … , p ( x k ) ) \Psi(x_1,\ldots,x_k)=P_0^{\mathrm{ml}}(p(x_1),\ldots,p(x_k)) Ψ ( x 1 , … , x k ) = P 0 ml ( p ( x 1 ) , … , p ( x k )) is Lipschitz with constant at most k q \sqrt{kq} k q ∑ i ∥ x i − y i ∥ 1 \sum_i\lVert x_i-y_i\rVert_1 ∑ i ∥ x i − y i ∥ 1 c c c k q kq k q k q t kqt k q t
r s ( k q t ) , r s ( u ) = C k q k q u λ / ( 18 log ( 1 / α ) ) . r_s(kqt),\qquad r_s(u)=C_{kq}\sqrt{kq}\,u^{\lambda/(18\log(1/\alpha))}. r s ( k q t ) , r s ( u ) = C k q k q u λ / ( 18 l o g ( 1/ α )) . In particular the error is independent of R R R
On the integral ensemble, H ( Z i ) ∈ S q H(Z_i)\in S_q H ( Z i ) ∈ S q Ψ \Psi Ψ (54) . On the common Gaussian ensemble, project H ( G u ) H(G_u) H ( G u ) S q S_q S q u ∈ U u\in U u ∈ U q q q u u u J J J Ψ \Psi Ψ opt q ( J ) \operatorname{opt}_q(J) opt q ( J ) c c c (53) .
Proof of Proposition A.2. We first derive estimates that hold for every R R R R R R 0 < κ < 1 / 2 0 < \kappa< 1/2 0 < κ < 1/2 q q q 1 / q ≤ μ 0 ( κ ) 1/q \le\mu_0(\kappa) 1/ q ≤ μ 0 ( κ ) λ = 2 κ \lambda= 2\kappa λ = 2 κ 0 < t < 1 / ( k q ) 0 < t < 1/(kq) 0 < t < 1/ ( k q ) χ > 0 \chi> 0 χ > 0
For an input graph Φ \Phi Φ π a → b \pi_{a\to b} π a → b a b ab ab
( π a → b z ) π a → b ( ℓ ) = z ℓ ( ℓ ∈ [ R ] ) . \left(\pi_{a\to b}z\right)_{\pi_{a\to b}(\ell)} = z_\ell\qquad(\ell\in[R]). ( π a → b z ) π a → b ( ℓ ) = z ℓ ( ℓ ∈ [ R ]) . The output variable set will be V = B × [ m ] R \mathcal{V} = B \times[m]^R V = B × [ m ] R a a a A A A b 1 , … , b k b_1,\ldots,b_k b 1 , … , b k N ( a ) N(a) N ( a ) Z ~ 1 , … , Z ~ k \widetilde{Z}_1,\ldots,\widetilde{Z}_k Z 1 , … , Z k
w i = ( b i , π a → b i Z ~ i ) ∈ V . (56) w_i = \left(b_i,\pi_{a\to b_i}\widetilde{Z}_i\right) \in\mathcal{V}. \tag*{(56)} w i = ( b i , π a → b i Z i ) ∈ V . (56) For any rank map f : V → Z f:\mathcal{V}\to\mathbb{Z} f : V → Z
V ( f ) = E P ‾ 0 ( f ( w 1 ) , … , f ( w k ) ) , V a ( f ) = E [ P ‾ 0 ( f ( w 1 ) , … , f ( w k ) ) ∣ a ] . V(f) = \mathbb{E}\,\overline{P}_0\left(f(w_1),\ldots,f(w_k)\right), \qquad V_a(f) = \mathbb{E}\left[\overline{P}_0\left(f(w_1),\ldots,f(w_k)\right)\mid a\right]. V ( f ) = E P 0 ( f ( w 1 ) , … , f ( w k ) ) , V a ( f ) = E [ P 0 ( f ( w 1 ) , … , f ( w k ) ) ∣ a ] . The bounded payoff (46) is used even if the experiment repeats an output ID. We will obtain a lower bound for one coarse rank map and an upper bound for every injective order, then transfer both bounds to distinct-variable constraints.
Suppose a labeling L L L 1 − ζ 1-\zeta 1 − ζ f ( b , z ) = z L ( b ) f(b,z)=z_{L(b)} f ( b , z ) = z L ( b ) a a a b b b
f ( b , π a → b z ) = z π a → b − 1 ( L ( b ) ) = z L ( a ) . f\left(b,\pi_{a\to b}z\right)=z_{\pi_{a\to b}^{-1}(L(b))}=z_{L(a)}. f ( b , π a → b z ) = z π a → b − 1 ( L ( b )) = z L ( a ) . Thus all k k k ( 1 − 2 κ ) k (1-2\kappa)^k ( 1 − 2 κ ) k k k k μ c \mu_c μ c
V ( f ) ≥ ( 1 − ζ ) ( 1 − 2 κ ) k v l o c . (57) V(f) \ge(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}. \tag*{(57)} V ( f ) ≥ ( 1 − ζ ) ( 1 − 2 κ ) k v loc . (57) For soundness fix an injective order O : V → [ ∣ V ∣ ] O:\mathcal{V}\to[|\mathcal{V}|] O : V → [ ∣ V ∣ ] a a a N ( a ) × [ m ] R N(a)\times[m]^R N ( a ) × [ m ] R M = h m R M=hm^R M = h m R O O O q q q C a , 1 , … , C a , q C_{a,1},\ldots,C_{a,q} C a , 1 , … , C a , q M / q M/q M / q q ∣ h q\mid h q ∣ h
F a j ( z ) = 1 h ∑ b ∈ N ( a ) 1 { ( b , π a → b z ) ∈ C a , j } , F a = ( F a 1 , … , F a q ) . (58) F_a^j(z)=\frac{1}{h}\sum_{b\in N(a)}\mathbf{1}_{\{(b,\pi_{a\to b}z)\in C_{a,j}\}}, \qquad F_a=(F_a^1,\ldots,F_a^q). \tag*{(58)} F a j ( z ) = h 1 b ∈ N ( a ) ∑ 1 {( b , π a → b z ) ∈ C a , j } , F a = ( F a 1 , … , F a q ) . (58) For every z z z F a ( z ) ∈ S q F_a(z)\in S_q F a ( z ) ∈ S q
E z F a j ( z ) = ∣ C a , j ∣ h m R = 1 q . (59) \mathbb{E}_z F_a^j(z)=\frac{|C_{a,j}|}{hm^R}=\frac{1}{q}. \tag*{(59)} E z F a j ( z ) = h m R ∣ C a , j ∣ = q 1 . (59) For any interval I I I
F a I ( z ) = 1 h ∑ b ∈ N ( a ) 1 { O ( b , π a → b z ) ∈ I } . F_a^I(z)=\frac{1}{h}\sum_{b\in N(a)}\mathbf{1}_{\{O(b,\pi_{a\to b}z)\in I\}}. F a I ( z ) = h 1 b ∈ N ( a ) ∑ 1 { O ( b , π a → b z ) ∈ I } . Call a pseudorandom at threshold t t t Inf ℓ ( T 1 − κ F a I ) ≤ t \operatorname{Inf}_{\ell}(T_{1-\kappa}F_a^I) \le t Inf ℓ ( T 1 − κ F a I ) ≤ t I I I ℓ ∈ [ R ] \ell\in[R] ℓ ∈ [ R ] a a a F a j F_a^j F a j
Let j a ( w ) j_a(w) j a ( w ) w w w
E b 1 , … , b k P ‾ 0 ( j a ( w 1 ) , … , j a ( w k ) ) = P 0 m l ( F a ( Z ~ 1 ) , … , F a ( Z ~ k ) ) . (60) \mathbb{E}_{b_1,\ldots,b_k}\overline{P}_0(j_a(w_1),\ldots,j_a(w_k))=P_0^{\mathrm{ml}}(F_a(\widetilde{Z}_1),\ldots,F_a(\widetilde{Z}_k)). \tag*{(60)} E b 1 , … , b k P 0 ( j a ( w 1 ) , … , j a ( w k )) = P 0 ml ( F a ( Z 1 ) , … , F a ( Z k )) . (60) The identity includes outcomes with equal neighbors. Further smoothing decreases the block influences, so Inf ℓ ( T 1 − 2 κ F a j ) ≤ t \operatorname{Inf}_{\ell}(T_{1-2\kappa}F_a^j)\le t Inf ℓ ( T 1 − 2 κ F a j ) ≤ t F a F_a F a opt q ( J ) + r s ( k q t ) \operatorname{opt}_q(J)+r_s(kqt) opt q ( J ) + r s ( k q t )
When the k k k O ( w i ) O(w_i) O ( w i ) i ≠ i ′ i\ne i' i = i ′
∑ j = 1 q E c E Z ∼ μ c R [ ( T 1 − 2 κ F a j ) ( Z i ) ( T 1 − 2 κ F a j ) ( Z i ′ ) ] . \sum_{j=1}^{q}\mathbb{E}_c\mathbb{E}_{Z\sim\mu_c^R}\left[(T_{1-2\kappa}F_a^j)(Z_i)(T_{1-2\kappa}F_a^j)(Z_{i'})\right]. j = 1 ∑ q E c E Z ∼ μ c R [ ( T 1 − 2 κ F a j ) ( Z i ) ( T 1 − 2 κ F a j ) ( Z i ′ ) ] . Conditional on c c c 1 / q 1/q 1/ q r c = r c m , κ r_c=r_c^{m,\kappa} r c = r c m , κ q − κ / 2 + q r c ( t ) q^{-\kappa/2}+qr_c(t) q − κ /2 + q r c ( t ) a a a
V a ( O ) ≤ S l o c : = opt q ( J ) + ( k 2 ) ( q − κ / 2 + q r c ( t ) ) + r s ( k q t ) . (61) V_a(O)\le S_{\mathrm{loc}}:=\operatorname{opt}_q(J)+\binom{k}{2}\left(q^{-\kappa/2}+qr_c(t)\right)+r_s(kqt). \tag*{(61)} V a ( O ) ≤ S loc := opt q ( J ) + ( 2 k ) ( q − κ /2 + q r c ( t ) ) + r s ( k q t ) . (61) We next turn an excess over this bound into a labeling of Φ \Phi Φ b ∈ B b\in B b ∈ B O O O { b } × [ m ] R \{b\}\times[m]^R { b } × [ m ] R o b o_b o b [ m ] R [m]^R [ m ] R
L b = { ℓ ∈ [ R ] : Inf ℓ ( T 1 − κ 1 { o b ( z ) ∈ I } ) > t / 2 for some rank interval I } . \mathcal{L}_b=\left\{\ell\in[R]:\operatorname{Inf}_{\ell}\left(T_{1-\kappa}\mathbf{1}_{\{o_b(z)\in I\}}\right)>t/2\text{ for some rank interval }I\right\}. L b = { ℓ ∈ [ R ] : Inf ℓ ( T 1 − κ 1 { o b ( z ) ∈ I } ) > t /2 for some rank interval I } . The few-influential-coordinates lemma [17 ] gives
∣ L b ∣ ≤ 400 κ ( t / 2 ) 3 = 3200 κ t 3 . (62) |\mathcal{L}_b|\le\frac{400}{\kappa(t/2)^3}=\frac{3200}{\kappa t^3}. \tag*{(62)} ∣ L b ∣ ≤ κ ( t /2 ) 3 400 = κ t 3 3200 . (62) This bound is uniform in R R R
If a a a I a I_a I a ℓ a \ell_a ℓ a Inf ℓ a ( T 1 − κ F a I a ) > t \operatorname{Inf}_{\ell_a}(T_{1-\kappa}F_a^{I_a})>t Inf ℓ a ( T 1 − κ F a I a ) > t
Inf ℓ a ( T 1 − κ F a I a ) ≤ 1 h ∑ b ∈ N ( a ) Inf π a → b ( ℓ a ) ( T 1 − κ 1 { O ( b , z ) ∈ I a } ) . (63) \operatorname{Inf}_{\ell_a}(T_{1-\kappa}F_a^{I_a})\le\frac{1}{h}\sum_{b\in N(a)}\operatorname{Inf}_{\pi_{a\to b}(\ell_a)}\left(T_{1-\kappa}\mathbf{1}_{\{O(b,z)\in I_a\}}\right). \tag*{(63)} Inf ℓ a ( T 1 − κ F a I a ) ≤ h 1 b ∈ N ( a ) ∑ Inf π a → b ( ℓ a ) ( T 1 − κ 1 { O ( b , z ) ∈ I a } ) . (63) Each term is at most one. An average greater than t t t t / 2 t/2 t /2 t / 2 t/2 t /2 π a → b ( ℓ a ) ∈ L b \pi_{a\to b}(\ell_a)\in\mathcal{L}_b π a → b ( ℓ a ) ∈ L b
Give each such a a a ℓ a \ell_a ℓ a L b ≠ ∅ \mathcal{L}_b\ne\varnothing L b = ∅ L b \mathcal{L}_b L b a a a
t 2 κ t 3 3200 = κ t 4 6400 . \frac{t}{2}\frac{\kappa t^3}{3200}=\frac{\kappa t^4}{6400}. 2 t 3200 κ t 3 = 6400 κ t 4 . One random right labeling is used for all left vertices. Linearity of expectation and the common left degree identify the resulting average with the ordinary uniform edge fraction.
If V ( O ) > S l o c + χ V(O)>S_{\mathrm{loc}}+\chi V ( O ) > S loc + χ χ \chi χ g g g 0 ≤ V a ( O ) ≤ 1 0\le V_a(O)\le1 0 ≤ V a ( O ) ≤ 1 (61) give V ( O ) ≤ ( 1 − g ) S l o c + g ≤ S l o c + g V(O)\le(1-g)S_{\mathrm{loc}}+g\le S_{\mathrm{loc}}+g V ( O ) ≤ ( 1 − g ) S loc + g ≤ S loc + g χ κ t 4 / 6400 \chi\kappa t^4/6400 χ κ t 4 /6400
val ( Φ ) ≤ ν < χ κ t 4 6400 ⟹ V ( O ) ≤ S l o c + χ for every injective O . (64) \operatorname{val}(\Phi)\le\nu<\frac{\chi\kappa t^4}{6400}\quad\Longrightarrow\quad V(O)\le S_{\mathrm{loc}}+\chi\quad\text{for every injective }O. \tag*{(64)} val ( Φ ) ≤ ν < 6400 χ κ t 4 ⟹ V ( O ) ≤ S loc + χ for every injective O . (64) It remains to turn the independent experiment into strict ordering constraints. Let D D D b 1 , … , b k b_1,\ldots,b_k b 1 , … , b k h ≥ k h\ge k h ≥ k
p D : = Pr ( D ) = ( h ) k h k , δ h : = 1 − p D ≤ ( k 2 ) h . (65) p_D:=\Pr(D)=\frac{(h)_k}{h^k},\qquad\delta_h:=1-p_D\le\frac{\binom{k}{2}}{h}. \tag*{(65)} p D := Pr ( D ) = h k ( h ) k , δ h := 1 − p D ≤ h ( 2 k ) . (65) The probability is the same at every a a a D D D D D D a a a ( h ) k (h)_k ( h ) k b i b_i b i I 0 I_0 I 0 P 0 P_0 P 0 OPT P 0 ( I 0 ) \operatorname{OPT}_{P_0}(I_0) OPT P 0 ( I 0 )
Let V D ( f ) V_D(f) V D ( f ) V ¬ D ( f ) V_{\neg D}(f) V ¬ D ( f ) f f f
V ( f ) = p D V D ( f ) + ( 1 − p D ) V ¬ D ( f ) , ∣ V D ( f ) − V ( f ) ∣ ≤ δ h , (66) V(f)=p_DV_D(f)+(1-p_D)V_{\neg D}(f),\qquad\lvert V_D(f)-V(f)\rvert\le\delta_h, \tag*{(66)} V ( f ) = p D V D ( f ) + ( 1 − p D ) V ¬ D ( f ) , ∣ V D ( f ) − V ( f )∣ ≤ δ h , (66) because all payoffs lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] (57) . Within each finite fiber of that map, choose one uniform random permutation of the distinct IDs, independently between fibers, and concatenate the fibers in rank order. On every conditioned tuple, restriction of these permutations to its IDs is uniform within each tied rank class. Thus the expected strict P 0 P_0 P 0 V D ( f ) V_D(f) V D ( f ) O O O P 0 P_0 P 0 (57) , (64) , and (66) therefore give the strict bounds
Y E S : OPT P 0 ( I 0 ) ≥ ( 1 − ζ ) ( 1 − 2 κ ) k v l o c − δ h , N O : OPT P 0 ( I 0 ) ≤ S l o c + χ + δ h if ν < χ κ t 4 6400 . (67) \begin{aligned}
\mathrm{YES}:&\quad\operatorname{OPT}_{P_0}(I_0)\ge(1-\zeta)(1-2\kappa)^k v_{\mathrm{loc}}-\delta_h,\\
\mathrm{NO}:&\quad\operatorname{OPT}_{P_0}(I_0)\le S_{\mathrm{loc}}+\chi+\delta_h\quad\text{if }\nu<\frac{\chi\kappa t^4}{6400}. \tag*{(67)}
\end{aligned} YES : NO : OPT P 0 ( I 0 ) ≥ ( 1 − ζ ) ( 1 − 2 κ ) k v loc − δ h , OPT P 0 ( I 0 ) ≤ S loc + χ + δ h if ν < 6400 χ κ t 4 . (67) These bounds are for the conditioned P 0 P_0 P 0 (47) makes every occurrence use the original predicate Π \Pi Π I I I
We now make the choices for the prescribed δ \delta δ η \eta η 10 η < δ 10\eta<\delta 10 η < δ 0 < κ < 1 / 2 0<\kappa<1/2 0 < κ < 1/2 2 κ k < η 2\kappa k<\eta 2 κk < η K = ( k 2 ) K=\binom{k}{2} K = ( 2 k ) q q q
1 q ≤ μ 0 ( κ ) , K q − κ / 2 < η . \frac{1}{q}\le\mu_0(\kappa),\qquad Kq^{-\kappa/2}<\eta. q 1 ≤ μ 0 ( κ ) , K q − κ /2 < η . Choose the data J , m , α J,m,\alpha J , m , α (45) at error η \eta η R R R t < 1 / ( k q ) t<1/(kq) t < 1/ ( k q )
K q r c ( t ) < η , r s ( k q t ) < η . Kq r_c(t)<\eta,\qquad r_s(kqt)<\eta. K q r c ( t ) < η , r s ( k q t ) < η . Set χ = η \chi=\eta χ = η ζ , ν < 1 \zeta,\nu<1 ζ , ν < 1
ζ < η , ν < η κ t 4 6400 . \zeta<\eta,\qquad\nu<\frac{\eta\kappa t^4}{6400}. ζ < η , ν < 6400 η κ t 4 . and choose an integer H ≥ max { k , q } H \ge\max\{k,q\} H ≥ max { k , q } K / H < η K/H < \eta K / H < η k , Π , δ k,\Pi,\delta k , Π , δ h h h
For every h ≥ H h \ge H h ≥ H δ h < η \delta_h < \eta δ h < η (48) , Bernoulli’s inequality, and (67) give
Y E S : OPT Π ( I ) ≥ 1 − ζ − 2 κ k − η − δ h > 1 − 4 η > 1 − δ , \mathrm{YES}: \quad\operatorname{OPT}_{\Pi}(I) \ge1-\zeta-2\kappa k-\eta-\delta_h > 1-4\eta> 1-\delta, YES : OPT Π ( I ) ≥ 1 − ζ − 2 κk − η − δ h > 1 − 4 η > 1 − δ , whereas (61) gives
N O : OPT Π ( I ) ≤ S l o c + χ + δ h < ρ Π + 6 η < ρ Π + δ . \mathrm{NO}: \quad\operatorname{OPT}_{\Pi}(I) \le S_{\mathrm{loc}}+\chi+\delta_h < \rho_{\Pi}+6\eta< \rho_{\Pi}+\delta. NO : OPT Π ( I ) ≤ S loc + χ + δ h < ρ Π + 6 η < ρ Π + δ . This proves the numerical claims simultaneously for every R R R
Finally we specify the encoded transformation. Once R R R c c c μ c ⊗ R \mu_c^{\otimes R} μ c ⊗ R 2 κ 2\kappa 2 κ θ R \theta_R θ R ξ \xi ξ B B B [ ∣ B ∣ ] [|B|] [ ∣ B ∣ ] V = B × [ m ] R V=B\times[m]^R V = B × [ m ] R a ∈ A a\in A a ∈ A ξ ∈ supp θ R \xi\in\operatorname{supp}\theta_R ξ ∈ supp θ R (56) , permuted by (47) , with weight
θ R ( ξ ) ∣ A ∣ ( h ) k . (68) \frac{\theta_R(\xi)}{|A|(h)_k}. \tag*{(68)} ∣ A ∣ ( h ) k θ R ( ξ ) . (68) The weights sum to one and are nonnegative rationals. Every listed tuple has distinct IDs; the same tuple may occur in several entries. There are ∣ B ∣ m R |B|m^R ∣ B ∣ m R ∣ A ∣ ( h ) k ∣ supp θ R ∣ |A|(h)_k|\operatorname{supp}\theta_R| ∣ A ∣ ( h ) k ∣ supp θ R ∣ k , m , R , θ R k,m,R,\theta_R k , m , R , θ R h h h θ R \theta_R θ R O ( log ∣ A ∣ + k log h ) O(\log|A|+k\log h) O ( log ∣ A ∣ + k log h ) O ( log ∣ B ∣ ) O(\log|B|) O ( log ∣ B ∣ ) R R R
The same occurrence-list encoding also justifies the deterministic random-order guarantee in Section 8. Build an order by exposing one next variable at a time. If exactly s s s Π \Pi Π s s s ( k − s ) ! (k-s)! ( k − s )! S k S_k S k ∣ Π ∣ / k ! |\Pi|/k! ∣Π∣/ k ! k k k
