Historical context and ingredients

Austrin, O’Donnell, Tan and Wright established perfect-completeness 2-to-1 Label Cover hardness with alphabets of sizes \(6\) and \(3\) and soundness \(23/24+\varepsilon\) (Austrin et al. 2014, Theorem 1.3, author manuscript). The remaining issue was to make soundness arbitrarily small while retaining both perfect completeness and two-element fibers.

The near-perfect-completeness theorem arose from the Grassmann and shortcode program. Khot, Minzer and Safra introduced a Grassmann-based candidate reduction (Khot et al. 2025); Dinur, Khot, Kindler, Minzer and Safra developed the reduction to a Grassmann agreement hypothesis and the associated expansion problem (Dinur et al. 2018, 2021). Barak, Kothari and Steurer related the agreement problem to expansion through the shortcode viewpoint (Barak et al. 2019). The near-perfect expansion theorem of Khot, Minzer and Safra completed these ingredients, giving completeness arbitrarily close to one and arbitrarily small soundness (Khot et al. 2023). More recently, Fei, Minzer and Wang proved perfect-completeness hardness for 4-to-1 games at arbitrarily small fixed soundness (Fei et al. 2026, Theorem 1.6).

Our conclusion concerns ordinary 2-to-1 games. In the Rich 2-to-1 framework of Braverman, Khot and Minzer, a uniformly random edge incident to each fixed left vertex must induce a partition that is uniform among all partitions of the left alphabet into pairs (Braverman et al. 2021, Definition 5). No such condition is part of Theorem 1. For any positive real soundness target, one may apply the theorem with a smaller fixed rational target.

Our external theorem inputs are a perfect-completeness PCP gap, projection-game parallel repetition, and Grassmann expansion (Dinur 2007; Dinur and Steurer 2014; Khot et al. 2023). From the last input we derive the inverse shortcode estimates using the chart and averaging arguments of Barak, Kothari and Steurer (Barak et al. 2019); Section 2 gives the forms needed here. The sampling comparisons have antecedents in the sub-code covering framework of Khot and Safra (Khot and Safra 2013). The passage from agreement of restricted bilinear forms to a fixed form of bounded rank has a close counterpart in Fei, Minzer and Wang (Fei et al. 2026, Lemmas 5.15–5.16). We prove the comparisons needed for the function spaces and sampling laws below.

Proof overview

We start with a clause-versus-variable game: the left player answers a clause with a satisfying assignment to its variables, the right player answers a variable with a bit, and the constraint checks their agreement on that variable. A perfect-completeness PCP and parallel repetition make the source value a fixed small constant on NO inputs. We place independent copies of its questions at the leaves of a finite rooted tree. Each leaf carries all binary functions on its local answer domain. At an internal node we take the sum of the spaces spanned by products of pairs of functions from each child. In particular, the product of two functions from one descendant space belongs to every space above that descendant.

At every nonleaf node we display an array, meaning a list of functions from its space. A question is the unordered partition of the product of all leaf-answer domains according to the joint evaluation of these arrays. A legal answer is a nonempty part, so one assignment realizes all its restored outputs simultaneously. We discard input coordinates that these evaluations cannot distinguish; a clause coordinate seen only through one variable is recorded by that variable. This identifies a question on projected source domains with its pullback to the original domains. Deleting one binary output direction merges at most two parts and gives the preliminary at-most-two constraints. A satisfying source assignment answers every constraint. The same joint partitions also remain unchanged when an upper row is shifted by products of displayed lower rows, forcing exact identities on all restored responses. Section 3 defines the questions, their sampling law, and these identities.

To analyze soundness, we sample a random root-to-leaf path. Arrays off that path are uniform; arrays on it use a recursive sampler with fresh randomness for every call. Stopping the calls at a node expresses every ancestor array as a deterministic function of a bounded number of draws there. Increasing the number of children hides the special path child and makes the observed draws close to uniform. A separate comparison replaces the source questions below a small random set of children by their right questions. After lifting the resulting functions to the original domains, this change also has small total variation. Section 4 proves these comparisons and bounds the chance that a child selected from the observed functions was projected.

Suppose a labeling satisfies a fixed positive fraction of the preliminary constraints. With enough levels, some pair of levels has positive simultaneous success. At the upper level an inverse shortcode theorem finds one response occurring with positive density on an affine slice. The table records responses at every lower-level descendant of the upper node, so its range may be large; Theorem 9 has constants independent of that range and also applies to small quotient spaces. Joint partition identities convert the slice into a coset of linear functionals \(z\) on the upper function space with \(z(1)=1\). Each functional defines a product form \(F(g,h)=z(gh)\) on the lower function space. For the displayed lower rows \(s_1,\ldots,s_\ell\) and their restored response \(y\), joint legality gives \[\bigl(F(s_t,s_u)\bigr)_{t,u}=yy^{\mathsf t},\] so this tested matrix has rank at most one. A Fourier decoder on the projected side selects from a bounded list computed under a small-bias law determined by its own local input (Lemma 26). The two local forms agree after projection with fixed positive probability. Section 5 constructs these decoders, with an agreement bound independent of the lower row count.

The remaining difficulty is that the left form depends on the very rows on which its rank is tested. Passing that test therefore does not immediately bound its full rank. Resampling within the lower omitted-direction fiber gives equal restrictions with positive probability. The sparse-projection posterior bound promotes this to equality of full forms, apart from a small error. A second inverse application then finds one output form occurring densely on an affine slice of row lists. A fixed high-rank form almost never has a tested matrix of rank at most one on that slice. Thus a positive part of the agreement must come from bounded-rank forms (Section 6).

A low-rank normalized product form selects a short odd list of answers at each source leaf. On a projected leaf, agreement gives the parity pushforward of that list: retain exactly those right answers having an odd number of preimages in the left list. Some projected children have all their sampled contributions equal to zero. After exposing the other data, both decoders can reconstruct their original inputs from their own questions at designated leaves in these children. The designated source pairs remain independent because the probability of the zero event is exactly independent of them (Lemmas 32 and 33). Projection-game repetition then contradicts positive agreement (Section 7).

Finally, Section 8 chooses the constants in their dependency order, completes at-most-two maps to exact 2-to-1 maps, and replaces rational edge weights by an explicit unweighted multiset.

Applications

The next corollary recovers Håstad’s unconditional hardness theorem for satisfiable Not-Two and the corresponding three-query PCP consequence (Håstad 2014, Theorem 4.3), using the earlier reduction of O’Donnell and Wu.

Corollary 3 also follows by applying the O’Donnell–Wu reduction to Fei, Minzer and Wang’s perfect 4-to-1 theorem (Fei et al. 2026).

Through Guruswami and Sandeep’s reduction at \(d=2\) (Guruswami and Sandeep 2020, Theorem 1), Theorem 1 also recovers the known NP-hardness of distinguishing three-colorable graphs from graphs that are not \(c\)-colorable, for every fixed integer \(c\ge3\) (Fei et al. 2026, Corollary 1.7); the companion (OpenAI 2026, Theorem 1.1) separately proves stronger independent-set soundness with three-colorable completeness.

Finite projection games and the source gap

A finite projection game \(G\) consists of disjoint finite question sets \(U,V\), nonempty finite answer sets \(L_u,R_v\), a nonempty finite set of edge occurrences \(\mathcal E\), and a probability distribution \(\mu\) on \(\mathcal E\). An occurrence \(e\) has endpoints \(u(e),v(e)\) and a total map \(\pi_e:L_{u(e)}\to R_{v(e)}\). Distinct occurrences may have the same endpoints and different maps. A deterministic strategy is a pair of functions selecting \(a(u)\in L_u\) and \(b(v)\in R_v\), and \[\mathop{\mathrm{val}}(G)=\max_{a,b}\Pr_{e\sim\mu} [\pi_e(a(u(e)))=b(v(e))].\] Thus each player receives only its own question, and neither receives the edge occurrence unless that information is already determined by its question. Question-dependent legal answer sets are part of the definition. Zero-weight occurrences may be discarded. Isolated questions, when retained to define auxiliary tables, do not affect value. Independent private randomness, or shared randomness independent of the sampled edge, cannot increase value: fix complete answer functions for all questions using the random tapes, and average their deterministic success probabilities.

For \(k\geq1\), the game \(G^{\otimes k}\) samples \(k\) independent occurrences. Each player receives its ordered tuple of questions and returns a tuple of legal answers; acceptance requires all \(k\) constraints. The answer coordinates remain separate even when a question is repeated. We also set \(\mathop{\mathrm{val}}(G^{\otimes0})=1\).

Raz proved exponential decay under parallel repetition for general two-player games (Raz 1998); Holenstein simplified that proof (Holenstein 2009), and Rao obtained an alphabet-independent bound for projection games (Rao 2011). The precise estimate above is the parallel repetition theorem of Dinur and Steurer (Dinur and Steurer 2014, Corollary 1.2). Their Sections 2.1–2.2 allow nonnegative weights and parallel edges and use independent products of questions. Interchanging the players matches our projection direction. To express question-dependent answer sets in their common-alphabet convention, embed all legal answers in one finite alphabet and give illegal answers no accepting pairs. Such partial projection constraints are allowed there, and legal defaults show that this extension does not change value. Thus the stated version applies directly to our games.

We now specify the source questions, because their exact local domains will matter in the construction. For a normalized clause occurrence \(C\), let \(\mathcal A_C\subseteq\mathbb F_2^3\) be its seven satisfying assignments, recorded as variable bits, including the signs of the clause only in the definition of \(\mathcal A_C\). The game \(G_\Psi\) samples a uniform clause occurrence \(C\) and a uniform position \(h\in\{1,2,3\}\). The left question is \(C\), with answer domain \(\mathcal A_C\); the right question is the variable ID at position \(h\), with answer domain \(\mathbb F_2\); and the projection selects the \(h\)th bit. The occurrence and selected position remain with the verifier.

A satisfying assignment to \(\Psi\) gives value one. Conversely, fix any right labeling, hence an assignment to the variables of \(\Psi\). At every clause it violates, any legal left answer differs from that assignment in at least one position. Therefore \[ \varphi\text{ unsatisfiable} \quad\Longrightarrow\quad \mathop{\mathrm{val}}(G_\Psi)\leq1-\gamma_0/3. \tag{2}\] For any required constant \(\sigma>0\), choose a fixed integer \(t\) with \((1-\gamma_0^2/144)^t\leq\sigma\) and take \[ G_{\mathrm{src}}=G_\Psi^{\otimes t}. \tag{3}\] Theorem 5 gives source soundness at most \(\sigma\), with perfect completeness. Its left question is an ordered tuple of clause occurrences, its answer domain is the product of their \(\mathcal A_C\), its right question is the corresponding tuple of variable IDs, and its right answer domain is always \(\mathbb F_2^t\). In particular, a repeated variable ID in a right question imposes no equality condition on the corresponding answer coordinates. Both answer-domain sizes, \(7^t\) and \(2^t\), are constants, and the explicit game has polynomial size because \(t\) is fixed.

Each \(\mathcal A_C\) projects onto both bits at any single position and onto all four bit pairs at any two distinct positions. Indeed, a clause excludes just one of the eight triples, and any prescribed pair has two extensions. Taking products proves that every source projection is surjective. The pair-surjectivity observation will also make the support reduction of function queries unambiguous.

Matrix slices and the Grassmann input

Let \(H\) be a finite vector space, put \(K=\mathbb F_2^\ell\), and identify \(K\otimes H\) with \(\mathop{\mathrm{Hom}}(H^*,K)\). Thus a matrix \(M\) is a list of \(\ell\) rows in \(H\), and \(Mq\in K\) evaluates those rows at \(q\in H^*\). For a linear map \(A:K\to\mathbb F_2^a\), the notation \(AM\) denotes its \(a\) specified combinations of rows. A row and column slice is a nonempty affine set \[ \mathcal S= \{M\in K\otimes H: AM=U,\ Mq_b=t_b\ (1\leq b\leq c)\}, \tag{4}\] where \(U\in\mathbb F_2^a\otimes H\), \(q_b\in H^*\), and \(t_b\in K\). There is no independence requirement on the rows of \(A\) or on the \(q_b\). We count specified row combinations and column values, rather than their ranks; redundant equations can always be removed. A slice with no column constraints is a row fiber.

For \(a\in K\) and \(h\in H\), write \(ah=a\otimes h\). The matrix step used below is \[M\longmapsto M+ah, \qquad M\text{ uniform},\quad a\text{ uniform in }K\setminus\{0\},\quad h\text{ uniform in }H,\] with the three choices independent. This step is stationary: both endpoints are uniform. The possibility \(h=0\) is retained.

We recall the precise structural theorem behind the matrix argument. The Grassmann graph on an \(N\)-dimensional binary vector space has the \(\ell\)-dimensional subspaces as its vertices; distinct vertices are adjacent when their intersection has dimension \(\ell-1\). For a nonempty vertex set \(S\), its retention is the probability that a uniform vertex of \(S\) has a uniformly chosen neighbor in \(S\).

For sets of density at most \(1/2\), this is Theorem 1.12 of Khot–Minzer–Safra in ECCC TR18-006, revision 2 (Khot et al. 2023), with expansion written as one minus retention; Definitions 1.8 and 1.10 give the expansion and interval conventions. If the set has density greater than \(1/2\), take \(A_0=\{0\}\) and \(B_0=\mathbb F_2^N\). This whole interval has co-order zero and density greater than \(1/2\), so replacing the cited density constant by its minimum with \(1/2\) proves the statement in that case too. The order of the dimension quantifiers is important. We next give the matrix-chart argument, as in (Barak et al. 2019, sec. 3), and then remove the column-dimension requirement explicitly.

Our eventual matrices may have very small column spaces, including quotient spaces of dimension zero. Adding unused columns preserves the matrix test, but a dense slice in the enlarged space can mix real and dummy columns. The next lemma describes its projection exactly.

Partial tables and many row fibers

A partial table with finite range \(\mathcal Y\) is a function \(f:K\otimes H\to\mathcal Y\cup\{\bot\}\), where \(\bot\notin\mathcal Y\) means undefined. A defined equality requires both endpoints to have the same value in \(\mathcal Y\); two undefined values never count.

We will need random row advice to encounter such a slice, rather than merely the existence of one slice somewhere in the table. The next erasure argument supplies exactly this averaged guarantee.

All three matrix conclusions apply to quotient spaces without any change of constants. In particular, when \(H\) is replaced by \(H/B\), the column functionals produced above belong to \((H/B)^*\); their pullbacks to \(H\) annihilate \(B\). The proof adds dummy columns to the quotient itself and removes them by Lemma 8, so no functional outside this annihilator is introduced.

Formal slots and pointwise spaces

Let the source game be the fixed power of the clause–variable game from Section 2, and let \(t\geq1\) denote its power. A source left question is an ordered tuple of \(t\) clause occurrences. For a clause occurrence \(c\), write \(v(c,1),v(c,2),v(c,3)\) for its three distinct variable IDs in their specified order, and let \[\Omega_c=\mathcal A_c=\{x\in\mathbb F_2^3:x\text{ satisfies }c\}.\] These are actual variable values, with the literal signs accounted for in the satisfaction condition. Thus \(|\Omega_c|=7\), and every coordinate map \(x\mapsto x_j\), and every pair of distinct coordinate maps, is surjective. A source edge chooses one position in each clause. Its right question is the resulting ordered tuple of variable IDs and its answer domain is \(\mathbb F_2^t\). Coordinates of this domain remain separate even when two IDs agree.

Fix positive integers \(d,n_1,\ldots,n_d\), row counts \(\ell_1,\ldots,\ell_d\), and product counts \(R_1,\ldots,R_d\). Let \(\mathcal T\) be the rooted ordered tree with a single root at level \(d\), leaves at level \(0\), and exactly \(n_p\) children at every level-\(p\) node. Write \(\mathcal T_p\) for its level-\(p\) nodes, and set \(K_p=\mathbb F_2^{\ell_p}\). Every location in this fixed tree is part of its indexing, independently of the question ID placed there.

Let \(E\) be a tuple of source left questions, one at each leaf. Its elementary slots are the formal pairs \((C,k)\) with \(C\in\mathcal T_0\) and \(k\in[t]\). If the clause occurrence at this slot is \(c\), its domain is \(\Omega_c\). All slots are distinct factors of a Cartesian product: repeated clause or variable IDs impose no equality constraint between their answer coordinates. For any node \(D\), let \(\Omega_D(E)\) be the product of the elementary-slot domains below \(D\), and write \(\Omega(E)\) for the root domain.

We will also use a mixed tuple \(O\) obtained by replacing some leaf left questions by source right questions along specified source edges. At a projected elementary slot the domain is \(\mathbb F_2\), tagged with the selected variable ID. Write \(\Omega_D(O)\) and \(\Omega(O)\) for the resulting products. The selected coordinate maps give a surjection \[\pi_D:\Omega_D(E)\longrightarrow\Omega_D(O).\] Neither the formal location nor the independence of the answer coordinates is changed by projection. For example, the right question \((v,v)\) has the legal answer \((0,1)\), although a completeness labeling will not use that answer.

We henceforth use these injective pullbacks without writing their symbols. No assertion that the summands in (12) form a direct sum is intended. In particular their copies of the constant function coincide.

Joint evaluations and canonical questions

An array at a level-\(p\) nonleaf node \(D\) is an element \(M_D\in K_p\otimes H_D(E)\), equivalently an ordered list of \(\ell_p\) rows in \(H_D(E)\). At \(x\in\Omega(E)\), its evaluation is the vector \(M_D(x)\in K_p\). The full question function of an array family \(\mathbf M=(M_D)_{D\in\mathcal T,\,D\text{ nonleaf}}\) is \[ \Psi_{E,\mathbf M}:\Omega(E)\longrightarrow \prod_{p=1}^d\prod_{D\in\mathcal T_p}K_p, \qquad x\longmapsto (M_D(x))_D. \tag{14}\] Every nonleaf output occurs in this tuple.

For a nonleaf node \(D\) at level \(p\) and a nonzero direction \(a\in K_p\), let \(Q_{D,a}\) act on the output product in (14) by the quotient map \(K_p\to K_p/\mathop{\mathrm{span}}\{a\}\) at the \(D\) block and by the identity at every other block. Define \[ \Psi^{D,a}_{E,\mathbf M}=Q_{D,a}\Psi_{E,\mathbf M}. \tag{15}\] The quotient merges at most two attained output values. To turn this observation into a game constraint, we must first specify which representations of a joint function give the same question and which answers are legal.

We now turn an array-valued function into a question without retaining unobservable metadata. The construction applies to any finite-valued function \(f:\Omega(Q)\to Y\) on a mixed product domain, and in particular to both functions (14) and (15). The codomain \(Y\) may be a product of vector spaces and quotient spaces.

An elementary slot \(s\) is unused by \(f\) if changing only its argument never changes \(f\). A clause slot with domain \(\Omega_c\) is reducible to position \(j\) if, for every fixed choice \(x_{-s}\) of all other arguments and every \(u,u'\in\Omega_c\) with \(u_j=u'_j\), \[ f(x_{-s},u)=f(x_{-s},u'). \tag{16}\] Thus one fixed position \(j\) must work for the whole joint function, for all choices of the other arguments.

The global quantifier in (16) cannot be replaced by a sectionwise choice of position. For example, on \(\Omega_c\times\mathbb F_2\) the function \(f(x,b)=(1+b)x_1+bx_2\) uses one clause position in each fixed-\(b\) section, but has no single position through which it factors globally. The canonical reduction retains its clause slot. Pair-surjectivity proves uniqueness when a global factorization exists; it does not turn these different sectionwise choices into one factorization.

The reduced domain has explicit typed coordinates. At a retained full clause slot we record its formal location, clause occurrence ID and triple domain. At a retained bit slot we record its formal location and variable ID, with domain \(\mathbb F_2\). When a clause slot is reduced to a bit, its clause occurrence and selected position are discarded. Unused locations are discarded. Retained locations are kept in the fixed tree-and-slot order, so equal IDs in distinct slots are never merged. Let \[ \mathcal P_f= \{\widetilde f^{-1}(y):y\in\mathop{\mathrm{im}}f\} \tag{17}\] be the unordered partition of this reduced domain into nonempty fibers. The canonical key \(\mathfrak k_L(f)\) consists of a left-side tag, the retained typed coordinates, and \(\mathcal P_f\). Define \(\mathfrak k_R(f)\) with a distinct right-side tag. The codomain \(Y\), names \(y\) of its values, array coordinates, source projection positions and any sampling choices are not additional fields of a key. The typed coordinates and finite subsets in (17) have ordinary deterministic finite encodings.

A legal label at this key is a part \(P\in\mathcal P_f\). At a particular representation \(f\) of the key, define its restored output by \[ \operatorname{out}_f(P)=y \quad\Longleftrightarrow\quad P=\widetilde f^{-1}(y). \tag{18}\] This is a bijection from legal labels to \(\mathop{\mathrm{im}}f\). In particular every restored joint response is realized by one \(x\in\Omega(Q)\): choose a point of the part and lift it through \(r_f\). We never allow separately legal block outputs that do not belong to the image of the whole joint function.

Take as vertices all keys of the indicated side obtainable from mixed tuples of source questions, arbitrary arrays in their prescribed spaces, and, on the right, one quotient at a nonleaf node in a nonzero direction. Every key used by the sampling law below belongs to this set. Keys never used by a test have zero incident weight and may be assigned any legal part. Equivalently, a labeling of the positive-weight vertices can always be extended to these auxiliary keys. Because the definition identifies keys before choosing labels, all such extensions retain the exact sharing identity of Lemma 14.

One-bit constraints and perfect completeness

Fix an array family on \(E\), a nonleaf node \(D\) at level \(p\), and \(a\in K_p\setminus\{0\}\). Put \(f=\Psi_{E,\mathbf M}\) and \(g=Q_{D,a}f\). The edge joins \(\mathfrak k_L(f)\) to \(\mathfrak k_R(g)\) and has the following map on legal parts: \[ \pi_{f,D,a}(P)= \operatorname{out}_g^{-1} \bigl(Q_{D,a}\operatorname{out}_f(P)\bigr). \tag{19}\] The argument of the inverse belongs to \(\mathop{\mathrm{im}}g\), since \(\operatorname{out}_f(P)\in\mathop{\mathrm{im}}f\). These edge records define the constraints that our game may use. We specify their sampling distribution at the end of this section. Distinct records may have identical endpoints and may be combined only when their actual maps agree.

The local label sets have a uniform finite bound once the parameters are fixed. Indeed, if \(N=|\mathcal T_0|\), every mixed answer domain has size at most \(7^{tN}\), so every legal partition has at most \(7^{tN}\) parts. The canonicalization and each edge map can be computed by enumerating these finite domains. Quantitative polynomial-time and weight-removal details will be given when the parameters have been chosen.

Algebraic identities forced by joint answers

Evaluation tables and folding are standard mechanisms in PCP constructions; see Bellare, Goldreich and Sudan (Bellare et al. 1998, sec. 3.3). Here the canonical joint partition forces an exact algebraic identity on every labeling. It allows an upper array to absorb products of already displayed descendant rows, including all relations among those products.

The use of all relevant descendant outputs in Lemma 18 will allow one upper quotient table to handle every possible lower node. A label always supplies those outputs together; selecting a single descendant is not part of the vertex key.

The distribution of tests

The low-rank, Hadamard-bucket viewpoint is inspired by Golowich’s construction (Golowich 2023), as mediated by Fei–Minzer–Wang (Fei et al. 2026). The sampler here is a recursive-product redesign with separate independent calls. We prove its sampling estimates below; no expansion theorem or identical sampler from those works is assumed.

We now choose an original tuple \(E\), an array family, a node, and an omitted direction to sample one of the preceding constraints. Sample a source left question independently at each leaf, using the source left marginal, and denote the resulting tuple by \(E\).

Independently of \(E\), sample a path \(\mathsf P=(D_d,D_{d-1},\ldots,D_0)\) by choosing \(D_{p-1}\) uniformly among the children of \(D_p\), successively for \(p=d,\ldots,1\). We next define scalar laws conditional on \(E\) and this whole path. The procedure \(\operatorname{Sample}(D_p)\) returns a function in \(H_{D_p}(E)\). At \(p=0\) it returns an independent uniform element of \(H_{D_0}(E)\). At \(p\geq1\), write \(C_*=D_{p-1}\) for the path child and make the following independent draws: \[U_C\sim\operatorname{Unif}(H_C(E)^2)\quad(C\neq C_*), \qquad G_h,H_h\sim\operatorname{Sample}(C_*)\quad(1\leq h\leq R_p).\] Return \[ \operatorname{Sample}(D_p) =\sum_{C\neq C_*}U_C+\sum_{h=1}^{R_p}G_hH_h. \tag{22}\] Its conditional law is denoted \(\nu_{D_p}\); the dependence on \(E\) and the path below \(D_p\) is suppressed in this notation. An empty sum over ordinary children is zero. By (12), every returned function lies in the claimed space.

Every invocation of \(\operatorname{Sample}\) uses a new random tape for the entire recursive call tree. In particular the two factors in one product, the factors in different products, and calls made on behalf of different displayed arrays are independent conditional on \(E,\mathsf P\). Visiting the same geometric node in two calls does not reuse a value. Uniform functions in ordinary children are drawn directly from the stated spaces; they do not refer to the displayed arrays in those children.

For every nonleaf path node \(D_p\), \(1\le p\le d\), independently take a fresh sample \(h_{p,v}\sim\nu_{D_p}\) for each \(v\in K_p\setminus\{0\}\) and set \[ M_{D_p}=\sum_{v\in K_p\setminus\{0\}}v\otimes h_{p,v}. \tag{23}\] We refer to the summands indexed by \(v\) as buckets; \(v\) is a bucket direction in \(K_p\), not a row map. For every nonleaf node off the path, take \(M_D\) uniform in \(K_{\operatorname{level}(D)}\otimes H_D(E)\). All these displayed arrays use separate random tapes. Thus, conditional on \(E,\mathsf P\), the displayed arrays are independent, including a path array and an ancestor array whose scalar calls pass through that path node. They need not be independent after the common path is averaged out. The same definitions apply to any mixed tuple \(O\) in its own function spaces. Later modifications will explicitly replace calls at a specified cut by uniform draws.

Figure 1, beside the decoder input definitions, depicts the two cuts and the distinction between a node and separate calls at that node.

Only the canonical key of the joint function (14) is supplied as the left question. The path, buckets, and internal tapes determine its distribution and are not appended to that key.

To specify all candidate tests on the sampled array family, draw independently \[a_p\sim\operatorname{Unif}(K_p\setminus\{0\}),\qquad 1\leq p\leq d,\] independently of the preceding data. At level \(p\) use the quotient \(Q_{D_p,a_p}\); abbreviate it to \(Q_{p,a_p}\). The actual test chooses \(p\) uniformly from \([d]\), independently, and uses the edge with left question \(\mathfrak k_L(\Psi_{E,\mathbf M})\), right question \(\mathfrak k_R(\Psi^{D_p,a_p}_{E,\mathbf M})\), and projection (19). This finite distribution of edge records defines the preliminary weighted game. Equivalently, one may draw only the direction belonging to the chosen level. Sampling all directions specifies a joint law of the candidate tests whose individual marginals are precisely this test.

By Proposition 16, the game has perfect completeness. The remaining sections prove its soundness by analyzing what a successful labeling reveals about the sampled arrays.

Stopping the ancestor generators

A scalar call means one invocation of the law \(\nu_D\) defined in Section 3, with its own fresh random choices. Write \(b_p=2^{\ell_p}-1\) and \(c_p=2R_p\). For a fixed path prefix ending at a node \(D_p\) of level \(p\), a call at a higher path node branches into exactly \(c_h\) independent calls at its path child when it crosses level \(h\). Its ordinary child contributions are uniform functions supported outside that child and require no calls farther down the distinguished path.

We will also use an equivalent representation after uniformizing the cut. Instead of generating \(M_{D_p}\) from \(b_p\) uniform buckets, generate its \(\ell_p\) rows as separate uniform draws. The relevant number of calls is then \[ \widehat T_p=\ell_p+ \sum_{k=p+1}^d b_k\prod_{h=p+1}^k c_h. \tag{26}\] We reserve \(\widehat T_p\) for the displayed original call family. If a comparison adds \(e\) independent uniform rows, where \(e\) is fixed, its enlarged count is \(\widehat T_p+e\). For instance, forming a uniform matrix together with one rank-one step from it requires its rows and one additional independent scalar draw, giving the count \(\widehat T_p+1\). These rows have separate tapes from the ancestor calls. If visibility of upper buckets will later be chosen by a row map \(A\), predetermine calls for all buckets before choosing which are visible. Selecting or discarding calls afterward adds no dependence to the count.

Finite child blocks and a hidden special child

Fix a level-\(p\) cut \(D=D_p\) and an integer \(t_{\mathrm{cut}}\) bounding all scalar draws retained at that cut. For a child \(C\) of \(D\), put \(V_C=H_C(E)^2\) and define the following finite product space: \[ \mathcal X_C=V_C^{t_{\mathrm{cut}}}\times \prod_{\substack{T\subseteq C\\T\text{ nonleaf}}} (K_{\operatorname{level}(T)}\otimes H_T(E)). \tag{27}\] Here \(T\subseteq C\) means that \(T\) is \(C\) or a descendant of \(C\). A block \(X_C\) records a separate child contribution to each of the \(t_{\mathrm{cut}}\) cut draws and the actual arrays throughout this child’s subtree. The factors used internally to generate a special contribution are not included in \(X_C\). Each recorded contribution is just a function in \(V_C\).

Let \(P_C\) be uniform on \(\mathcal X_C\). To construct independent uniform cut draws, sample these blocks independently and, for each draw, add its child contributions. This uses a latent product of spaces even though the actual spaces \(V_C\) share the constant functions. Indeed the map \[\prod_{C\text{ child of }D}V_C\longrightarrow H_D(E), \qquad (u_C)_C\longmapsto\sum_Cu_C\] is a surjective linear map. Every fiber is a coset of its kernel, so the image of uniform measure is uniform. Separate copies give independent uniform cut draws, independently of all descendant arrays. No direct-sum decomposition, or recovery of the summands from their sum, is asserted.

There is a uniform finite density bound for any law on \(\mathcal X_C\). For clarity, if the source’s legal assignment domains have size at most \(a\), put \(N_0=1\) and \(N_k=\prod_{h=1}^k n_h\). Every space on a level-\(k\) subtree has dimension at most \(a^{N_k}\). Thus, for children at level \(p-1\), \[ \dim\mathcal X_C\le D_p(t_{\mathrm{cut}}):=a^{N_{p-1}}\left(t_{\mathrm{cut}}+ \sum_{k=1}^{p-1}\ell_k\prod_{h=k+1}^{p-1}n_h\right). \tag{28}\] In particular we may use \(L_p(t_{\mathrm{cut}})=2^{D_p(t_{\mathrm{cut}})}\). Every probability law \(Q_C\) on \(\mathcal X_C\) has density \(q_C=dQ_C/dP_C\le L_p(t_{\mathrm{cut}})\), since each \(P_C\) atom has mass \(2^{-\dim\mathcal X_C}\). This bound uses the source alphabet, the fixed row and repetition counts through \(t_{\mathrm{cut}}\), and branching below \(p\). It uses neither \(n_p\), higher branching, source question identities, nor the source instance size. Any larger fixed common bound will also be denoted by \(L_p\).

In \(\mathsf U_p\), the own buckets are separate from the pending ancestor calls and the descendant matrices. The matrix \(M=\sum_{v\in K_p\setminus\{0\}}v h_v\) is uniform: the linear map from its uniform buckets onto \(K_p\otimes H_{D_p}(E)\) is surjective, since the standard basis vectors occur among the indices. Replacing \(h_a\) by an independent uniform \(h_a^*\), for an independent nonzero \(a\in K_p\), gives \[ M^*=M+a h,\qquad h=h_a+h_a^*. \tag{30}\] Conditional even on all old buckets, \(h\) is uniform and independent of the old data. Thus this is exactly the uniform rank-one step, and \(M\) is independent of the other displayed arrays and the pending ancestor calls. This conclusion would not follow by reusing a bucket as an ancestor call.

Sparse projection and its posterior

The next comparison is a form of sub-code covering: a sparse restriction leaves the lifted query law nearly unchanged. This method appears in Khot and Safra (Khot and Safra 2013, sec. 3.4), with advice-conditioned thinning estimates in Dinur, Khot, Kindler, Minzer and Safra (Dinur et al. 2018, Lemma 5.5, full version) and Fei, Minzer and Wang (Fei et al. 2026, Propositions 4.7–4.8 and 5.5). Here the independent units are entire child subtrees, whose records include all stopped-call contributions and displayed descendant arrays. We prove the comparison and posterior estimate for these finite blocks.

At a level-\(i\) cut \(D_i\), independently mark each child with probability \(\beta_i=n_i^{-2/3}\); take \(n_i>1\) to be a cube. At every leaf in a marked child, sample a source projection conditional on its left question, and replace that question by its right question. Leave all other questions unchanged, and call the resulting tuple \(O\). Pullback along these projections identifies \(H_T(O)\) with a subspace of \(H_T(E)\) and preserves pointwise multiplication. Define \(\mathsf M_i\), the modified experiment, by stopping all ancestor calls at \(D_i\) and making their values independent uniform draws in \(H_{D_i}(O)\). Also sample \(M_{D_i}\) and all its descendant matrices independently uniformly in the corresponding projected spaces. Reconstruct all ancestors by the original stopped expressions. Path choices below \(i\) are unused. Independent extra cut rows and bucket replacements are treated in the same way. The original unmodified law will be denoted by \(\mathsf A\).

Bias that is independent of dimension

Total variation above is obtained by increasing branching. The upper Fourier argument instead requires a small-bias bound before any slice conditioning, obtained by increasing the product counts. We use the character-wise notion of small bias of Naor and Naor (Naor and Naor 1993); the required sampler estimate is proved below. For a law \(\mu\) on a finite binary vector space \(V\), call it quarter-balanced if every nonzero \(f\in V^*\) satisfies \(\mathbb P_{x\sim\mu}(f(x)=b)\ge1/4\) for both \(b\in\mathbb F_2\).

The order of accuracy choices follows from this proof. At descendants one needs only the absolute quarter-balance guarantee, obtained by the common \(R_{\min}\). Once an upper level \(j\) requires a tolerance \(\lambda_j>0\), it suffices to choose \(R_j\) with \((7/8)^{R_j}\le\lambda_j\). No requested upper accuracy imposes a finer accuracy at a lower level. After all row counts, product counts and the source alphabet are fixed, choose branching upward. At cut \(p\), \(L_p\) is already fixed by lower branching, and \[\varepsilon_p^{\mathrm{cut}}\longrightarrow0, \qquad \varepsilon_p^{\mathrm{spr}}\longrightarrow0, \qquad \frac{2n_p^{-2/3}L_p}{1-n_p^{-2/3}}\longrightarrow0.\] For the middle limit, use \((1+n_p^{-4/3}L_p^2)^{n_p}\le\exp(L_p^2n_p^{-1/3})\). Enlarging higher branching changes only the exterior record and the reconstruction map, so all three bounds already secured at \(p\) persist.

Selecting two levels and a quotient table

Suppose that the labeling accepts with probability at least \(\varepsilon\), where \(0<\varepsilon<1\), and choose \(d\varepsilon\ge4\). If \(N=\sum_{p=1}^d\mathbf 1_{\mathrm{Acc}_p}\), then \[\mathbb E[N(N-1)]\ge (\mathbb EN)^2-\mathbb EN \ge d^2\varepsilon^2-d\varepsilon.\] Consequently some \(i<j\) satisfies \[ \mathbb P(\mathrm{Acc}_i\cap \mathrm{Acc}_j) \ge \frac{d^2\varepsilon^2-d\varepsilon}{d(d-1)} \ge \frac{3\varepsilon^2}{4}. \tag{37}\] No independence between the acceptance events is used here. Pass to the modified experiment at level \(i\) from Section 4: each child of \(D_i\) is independently projected with probability \(\beta_i=n_i^{-2/3}\), and all calls stopped at \(D_i\), its own matrix, and its descendant matrices are independent uniform draws in their new spaces. Write \(\mathbb P_i\) for this law, with all functions also pulled back to the original tuple \(E\). By Lemmas 20 and 21, we can require the comparison error in (37) to be at most \(\varepsilon^2/4\). Thus, throughout this section, \[ \mathbb P_i(\mathrm{Acc}_i\cap \mathrm{Acc}_j)\ge c,\qquad c=\varepsilon^2/2. \tag{38}\] All eventual parameter choices will satisfy the stated bounds for every possible pair \(i<j\).

The comparison at the upper cut forgets which level-\(i\) descendant lies on the path. We therefore build one response table using the displayed rows at every level-\(i\) descendant of \(D_j\). Put \(H=H_{D_j}(E)\), \(K=K_j=\mathbb F_2^{\ell}\), \(\ell=\ell_j\), and \(M=M_{D_j}\). The data \[P=(E,\text{path through }D_j,(M_D)_{D\ne D_j})\] contain actual functions on the original domains. The record \(P\) does not include an explicit tag for the selected level-\(i\) descendant of \(D_j\), and does not append the projection mask or the questions in \(O\). The retained arrays may carry statistical information about these latent choices; the law comparisons already apply to the entire retained record. Let \(\mathcal D_i(D_j)\) be the set of all level-\(i\) descendants of \(D_j\). Write \(s_{C,t}\in H_C(E)\) for row \(t\) of \(M_C\), where \(C\in\mathcal D_i(D_j)\) and \(1\le t\le\ell_i\). Define \[ B=B(P)=\mathop{\mathrm{span}}\bigl(\{1\}\cup \{s_{C,t}s_{C,u}:C\in\mathcal D_i(D_j),\ 1\le t,u\le\ell_i\}\bigr) \subseteq H. \tag{39}\] The inclusion follows from \(H_C^2\subseteq H_{D_j}\). Fix, by deterministic linear algebra on \(P\), a linear section \(s:H/B\longrightarrow H\) of the quotient map \(\pi:H\longrightarrow H/B\). Apply both maps row by row.

For \(\bar M\in K\otimes(H/B)\), query the left table with upper matrix \(s(\bar M)\) and all other matrices specified by \(P\). Retain the response \[ f_P(\bar M)=\bigl(u,(y_C)_{C\in\mathcal D_i(D_j)}\bigr), \qquad u\in K,\quad y_C\in K_i. \tag{40}\] Thus the response contains the upper evaluation and the evaluations at every level-\(i\) descendant, without a tag marking the selected descendant. This finite range can be large; none of our inverse bounds depends on its size.

To recover the response at the original matrix \(M\), put \(\bar M=\pi(M)\) and write \(\Delta=M-s(\bar M)\in K\otimes B\). Addition of \(\Delta\) to the upper rows is an invertible triangular transformation of the combined evaluation tuple, since each row of \(\Delta\) is a constant plus a sum of products of unchanged lower rows. Lemma 17 therefore shows that all \(y_C\) are unchanged and that the upper response changes from \(u\) to \(u+\Delta b_y\), where \(b_y\) evaluates the generators of \(B\) according to \(1\mapsto1\) and \(s_{C,t}s_{C,u}\mapsto (y_C)_t(y_C)_u\). This rule is a well-defined linear functional: one legal assignment realizes the entire representative response, and its evaluation respects every pointwise linear relation among the generators in (39).

Define a usefulness mark by \[ U(P,\bar M)=\mathbf 1\{\mathbb P_i(\mathrm{Acc}_i\mid P,\bar M)\ge\kappa\}, \qquad \kappa=c/2, \tag{41}\] setting it to zero off the support of the conditioning data. The conditional probability averages over the selected lower path, its omitted direction, the \(B\)-component of \(M\), and any other unexposed randomness. Define the partial table \(\widetilde f_P\) to equal \(f_P\) where \(U=1\), and to be undefined (\(\bot\)) elsewhere. We fix these marks once using \(\mathbb P_i\) and use exactly the same partial tables under all subsequent laws.

From row advice to a predictable upper response

Write \(\mathbb P_j^0\) for the unrestricted cut law in the last assertion of Lemma 24, with independent auxiliary choices appended as needed. Put \(\eta=\theta/2\). If the average conditional equality given \(P\) is at least \(\theta=2\eta\), the set of \(P\) for which it is at least \(\eta\) has probability at least \((\theta-\eta)/(1-\eta)\ge\eta\). Use the constants \(0<\alpha\le1\), \(r\ge1\) in Lemma 10 at equality threshold \(\eta\), obtained from Theorem 9 at threshold \(\eta/2\). Assume that \(\ell\) meets their largeness requirement.

Sample \(A\in\mathop{\mathrm{Hom}}(K,\mathbb F_2^r)\) uniformly and independently. For any \((P,A,C)\), where \(C\in\mathbb F_2^r\otimes(H/B)\), call the advice good if the row fiber \(A\bar M=C\) has a nonempty slice obtained by specifying at most \(r\) columns on which one defined value of \(\widetilde f_P\) has density at least \(\alpha\) in uniform slice measure. For each good advice choose, using fixed deterministic orders, column functionals \(q_1,\ldots,q_k\in(H/B)^*\), values \(v_1,\ldots,v_k\in K\), and a response \[t_*=(u,(y_C)_{C\in\mathcal D_i(D_j)}),\qquad k\le r,\] witnessing this condition. These choices depend only on the advice; they are not selected using the actual position within the column slice. The probability of good advice \((P,A,A\bar M)\) under \(\mathbb P_j^0\) is at least \[ g=\frac{\eta^2}{4}\,2^{-r\ell}. \tag{42}\] Indeed, the set of qualifying \(P\) has mass at least \(\eta\), and for each such \(P\) Lemma 10 gives good-advice probability at least \((\eta/4)2^{-r\ell}\). Row maps of deficient rank are allowed throughout.

Pull the chosen \(q_a\) back to \(H^*\) and put \(Z=\mathop{\mathrm{span}}\{q_1,\ldots,q_k\}\subseteq\mathop{\mathrm{Ann}}(B)\). The chosen response occurs on a nonempty set of legal representative queries, so the preceding joint-legality argument defines its functional \(b_y\in B^*\). Define \(z_0\in H^*\) by \[ z_0(b+s(\bar h))=b_y(b) \quad(b\in B,\ \bar h\in H/B). \tag{43}\] This uses the direct-sum decomposition \(H=B\oplus s(H/B)\). At every match to the selected response the restored upper output equals \[ Mz_0+u. \tag{44}\] Every \(z\in z_0+Z\) satisfies \[ z(1)=1,\qquad \bigl(z(s_{C,t}s_{C,u})\bigr)_{t,u} =y_Cy_C^{\mathsf t}\quad(C\in\mathcal D_i(D_j)). \tag{45}\] Thus the whole coset is normalized and has tested rank at most one at each of these descendants. Dependent generators in \(B\) cause no ambiguity; legality, rather than a choice of their representation, defined \(b_y\).

Define two events on \((P,A,M)\): \[\begin{align*} J&=\{\text{advice is good and }Mq_a=v_a\text{ for }1\le a\le k\},\\ I&=J\cap\{\widetilde f_P(\bar M)=t_*\}. \end{align*}\] Both events belong to \(\sigma(P,A,\bar M)\), since every \(q_a\) annihilates \(B\) and the witness uses only \((P,A,A\bar M)\). In particular, \(I\) asks for a representative-table match; it does not ask for a restored right answer to equal (44). For uniform \(M\) in a fixed nonempty row fiber, imposing \(k\) columns costs at most \(k\ell\le r\ell\) binary equations. Therefore, with \[ h_0=2^{-r\ell},\qquad q_0=gh_0, \tag{46}\] the reference law satisfies \[ \mathbb P_j^0(J)\ge q_0,\qquad \mathbb P_j^0(I)\ge\alpha\mathbb P_j^0(J). \tag{47}\] The entire definition of goodness and the chosen witnesses is now fixed. When evaluating \(I,J\) under another law we use these same predicates.

The affine witness now predicts the upper response with positive probability, and every functional in its coset is normalized and passes the lower rank test. To obtain two local decoders, we need a bounded collection of candidate functionals, computed from the right input, that contains the restriction of some functional in this coset to the projected space. The same collection must work for every compatible left witness.

The local inputs and the original hidden law

Here and below the experiment is \(\mathbb P_i\). Write \(H'=H_{D_j}(O)\), \(H_i=H_{D_i}(E)\), \(H_i'=H_{D_i}(O)\), and \(S=M_{D_i}\). Pullback identifies the primed spaces with subspaces of the unprimed ones, preserving products. Put \(W=\ker A\) and split the upper matrix into \[ M=M_{\rm known}+X,\qquad M_{\rm known}=\sum_{v\in K\setminus W}v\otimes h_v,\qquad X=\sum_{v\in W\setminus\{0\}}v\otimes h_v\in W\otimes H'. \tag{49}\] The known sum is determined without any bucket whose index lies in \(W\). In particular \(AM=AM_{\rm known}\).

We specify the two inputs exactly. Tree locations are retained in these analytical inputs, even though the original partition keys omit unnecessary sampling metadata. The left information is \[ \mathcal L=\sigma\bigl(E,\text{path through }D_i,A, (M_D)_{D\ne D_j},(h_v)_{v\in K\setminus W}\bigr), \tag{50}\] where every function is represented on its original \(E\)-domain. These data supply \(S\) in full, without supplying \(a_i\), \(O\), or the projection choices as additional fields. The right information is \[ \mathcal R=\sigma\bigl(O,\text{path through }D_i,A,a_i, (M_D)_{D\ne D_j,D_i},S\bmod\langle a_i\rangle, (h_v)_{v\in K\setminus W}\bigr), \tag{51}\] with functions represented on their \(O\)-domains. The right is supplied only the displayed quotient of \(S\), with no additional missing-component ingredients. Neither side is supplied \(X\). The left can compute \(P\) and \(A\bar M\) from (50), so it can compute the good-advice predicate and its chosen witness without knowing \(M\). Figure 1 summarizes these information restrictions.

For clarity, the independence underlying these inputs is exact, not an approximation. Conditional on \(O\), the projection choices, and the path through \(D_i\), give each actual node matrix its own random tape. Give each scalar bucket in a matrix a fresh recursive call tree, with independent ordinary-child uniforms and independent factor calls at every product. All calls that reach \(D_i\) terminate in separate uniform draws in \(H_i'\). In particular, even a call used for an ancestor of \(D_j\) and a bucket of \(M\) that both visit \(D_j\) use disjoint random tapes. The product factorization of these tapes implies \[ (h_v)_{v\in W\setminus\{0\}}\mathrel{\perp\!\!\!\perp} \bigl((h_v)_{v\notin W},(M_D)_{D\ne D_j}\bigr) \quad\text{given the domains, path, and }A. \tag{52}\] The same statement remains true if the original questions \(E\) and the projection maps are additionally given: they determine the embeddings of the spaces but do not change the intrinsic \(O\)-space sampler. This also explains why analytical disclosure of the full \(S\) is harmless for this factorization, although \(S\) is not part of the right input.

Let \(\mu_{\mathcal R}\) be the distribution on \(W\otimes H'\) obtained by sampling the hidden buckets in (49) with this original modified-\(i\) sampler. It is a function of the right input alone. Indeed, the right knows \(O\), the path down to the terminating cut, all spaces and all sampler parameters. Independent recursive calls above that cut can be enumerated on those spaces without knowing \(E\), any projection map, or the missing part of \(S\). Formula (52) shows that \(\mu_{\mathcal R}\) is also the actual conditional hidden law after revealing all of the data in both inputs, including full \(S\).

For each fixed right input, define \[ G_{\mathcal R}:W\otimes H'\longrightarrow K \tag{53}\] by assembling the level-\(i\) right query with upper matrix \(M_{\rm known}+X\), consulting its fixed partition label, and restoring the upper component. This is a well-defined local function: the lower matrix in this query is precisely \(S\bmod\langle a_i\rangle\). The original labeling has already been extended to unused legal keys, so this definition is total for every \(X\) in the ambient space.

Assume that every product count meets the absolute balance minimum of Lemma 23, and that \[ (7/8)^{R_j}\le\lambda. \tag{54}\] Every nonzero character of \(W\otimes H'\) then has bias at most \(\lambda\) under \(\mu_{\mathcal R}\). To check this directly, identify a character with a nonzero linear map \(\Phi:W\longrightarrow(H')^*\). Some nonzero \(v\in W\) has \(\Phi(v)\ne0\), so its expectation on the corresponding bucket has absolute value at most \(\lambda\) by Lemma 23. Independence factors the expectation over all hidden buckets, and all remaining factors have absolute value at most one. This argument makes no claim about small bias after a slice, a successful match, or any later conditioning.

A bounded list for an arbitrary small-bias law

We record the Fourier calculation separately. It uses characters under their actual sampling law rather than treating small bias as total-variation closeness to uniform measure. The short-list principle is related to Goldreich–Levin heavy-character decoding (Goldreich and Levin 1989). We prove the needed statement for the present nonuniform, own-question law; no efficient decoding algorithm is required. If \(V=W\otimes H'\), write \[\chi_\Phi(X)=(-1)^{\langle\Phi,X\rangle},\qquad \Phi\in V^*=\mathop{\mathrm{Hom}}(W,(H')^*).\] For \(\sigma\in K^*\) and a fixed function \(G:V\longrightarrow K\), put \(g_\sigma(X)=(-1)^{\sigma(G(X))}\).

Constructing the two decoders

The algorithms in Proposition 27 are now fixed local rules. In particular, the right rule always computes its heavy lists from the original law \(\mu_{\mathcal R}\) just defined. A later conditioning may change the physical law of the hidden buckets; it does not change that algorithm. The subsequent rank and repetition arguments use these same rules with their prescribed inputs.

Local tapes and the unfiltered pair experiment

We first specify the randomness to be used without enlarging either decoder’s information. At the modified cut at \(D_i\), condition on \(E,O\), the projections and the path through \(D_i\). The advice outside the list \(S\) is generated by independent exterior ingredients, independent uniform descendant arrays in their projected spaces, and a bounded number of independent uniform scalar calls in \(H_i'\). The scalar calls generate all dependencies of ancestor arrays and the visible level-\(j\) buckets. The list \(S\) uses fresh randomness independent of all these calls. This uses the stopped-call representation of Lemma 19, with the independent cut rows in the modified experiment defined before Lemma 21. In particular, already assembled ancestor arrays are functions of these calls and the exterior ingredients; they are not additional independent exterior variables.

The direct-row representation in Equation (26) uses \(\widehat T_i\) scalar cut rows, including the rows of \(S\). The lower resampling below adds one independent row, giving the count \(\widehat T_i+1\) for that comparison. Calls may be included before the row map \(A\) selects which level-\(j\) buckets are visible. Thus their number depends on the fixed row and product counts, and not on \(n_i\) or on branching at higher levels.

The left decoder receives \(E\), the path through \(D_i\), its displayed arrays including \(S\), the upper row map \(A\), and the prescribed visible upper buckets as functions on its own domains. It receives neither \(O\), the projection choices, nor the omitted lower direction \(a_i\). The right decoder receives its corresponding data on \(O\), together with \(a_i\) and \(S\bmod a_i\), and receives no ingredients determining the missing part of \(S\). The latent data just described are an analytical representation of these inputs, not additional inputs to the decoders.

A complete local random tape specifies the decoder’s random choices on every possible local input. Since all input and output sets are finite, each randomized decoder is a distribution on deterministic local functions. Averaging therefore permits fixing both complete tapes while preserving any hypothesized unconditional agreement probability. Such a fixing does not condition on a realized answer or on an agreement event. For a cutoff \(s\), erase a left output if it is not admissible at its own input or if its full rank is at most \(s\). This erasure depends only on the left input and its fixed tape.

We have converted substantial high-rank agreement into equality of one partial table under an ordinary rank-one step. The inverse theorem will select a single output form dense on a row/column slice. The next lemma shows that a fixed form of high rank cannot pass the tested rank condition on such a slice, even when its free rows have affine offsets.

A rank bound on affine slices

Positive agreement of bounded-rank forms

The resulting agreement event supplies a normalized product form of bounded full rank. Its restrictions to the atomic indicators at a leaf will produce an odd list of at most \(s\) legal answers. The next section turns those lists into local strategies on many independent source questions.

Odd lists and leaf indicators

For a finite nonempty set \(\Lambda\), define \[\mathcal O_s(\Lambda) =\{L\subseteq\Lambda:1\le |L|\le s, |L|\text{ odd}\}.\] Given a map \(\pi:\Lambda\to\Gamma\), define its parity pushforward by \[ \pi_{\mathrm{odd}}(L) =\{b\in\Gamma:|L\cap\pi^{-1}(b)|\text{ is odd}\}. \tag{76}\] The same parity pushforward describes restriction of Fourier characters in low-degree long-code analysis (Dinur and Guruswami 2015, sec. 2.3, Equation (1), ECCC version). The odd-list game \(G_{\mathrm{odd},s}\) has the same questions and edge distribution as \(G_{\mathrm{src}}\), legal answers \(\mathcal O_s(\Lambda_u)\) and \(\mathcal O_s(\Gamma_v)\), and edge map \((\pi_e)_{\mathrm{odd}}\).

Low-rank symmetric matrices also yield short assignment lists in the quadratic-code analysis of Khot and Saket, through rank-one decompositions (Khot and Saket 2017, Lemma 2.1 and Section 7.2, ECCC version). Here the orthogonal leaf indicators give the lists directly as diagonal supports of legal answers.

We use a total local extraction rule also when a decoder fails to return such a form. Order the legal answers to every source question once and for all. At each designated leaf, a player reads the diagonal support of its own output form. If that support is odd and has size at most \(s\), it returns the support. If the output is not a form or this test fails, it returns the singleton consisting of the first legal answer to its own question. The test and default use only that player’s input and output. In particular, the right player need not determine the rank or validity of the left form. These rules produce legal lists on every input, and Lemma 31 identifies their outputs whenever normalized low-rank agreement occurs.

An exact law for vanishing advice

Zero advice was already used to hide a source coordinate and recover soundness under repetition by Khot, Minzer and Safra (Khot et al. 2025, secs. 3.3–3.4, especially Remark 3.2). Here we zero all sampled contributions from selected children and prove that the resulting conditional source law is exactly a product law.

Choose the first leaf of each child of \(D_i\) as its designated leaf. This choice depends only on the ordered tree. We will express every uniform cut draw as a sum of independent child contributions. A projected child will be clean when all its contributions and all its internal arrays are zero. Its arguments then disappear from the sampled functions, while the zero probability can be computed on that child’s projected domain.

The family of contributions must cover every input used by the decoders. Stop every recursive scalar call used by an ancestor array when it first reaches \(D_i\), including the calls for every bucket of \(M=M_{D_j}\). Fix this family before the row map \(A\) selects visible buckets, and add the \(\ell_i\) independent rows of the uniform matrix \(S\). By Equation (26), its size is \[ T_i^{\mathrm{cl}}=\widehat T_i=\ell_i+ \sum_{h=i+1}^{d}(2^{\ell_h}-1) \prod_{p=i+1}^{h}(2R_p). \tag{79}\] Indeed, an array at level \(h\) has \(2^{\ell_h}-1\) scalar buckets, and each scalar call at level \(p>i\) makes \(2R_p\) calls in its path child. All other contributions lie outside \(D_i\), and distinct calls use fresh randomness. If a recipe uses fewer calls, pad it with independent unused calls to reach \(T_i^{\mathrm{cl}}\). Thus the call count is fixed before any visibility decision. The notation \(T_i^{\mathrm{cl}}\) distinguishes this family from those enlarged by extra rows in comparison experiments.

Let \(\Xi\) record the questions outside \(D_i\), the path through \(D_i\), the exterior ingredients of the stopped expressions, and all other arrays supported outside \(D_i\). Include the independent choices \(A\) and \(a_i\) after fixing the call family. Record each exterior function on the domain of its supporting subtree, together with its location in the expression. This representation requires no endpoint questions inside \(D_i\); each player will later extend it to its own product domain by ignoring the other arguments. Assembled ancestor values are still functions of the pending cut calls and are not exposed in \(\Xi\). Consequently \(\Xi\) depends only on exterior source records and independent exterior randomness, so the source samples inside \(D_i\) retain their independent laws conditional on \(\Xi\).

It is convenient to sample a complete source edge at every leaf, even when its child will remain unprojected. This merely augments the modified experiment: sample the left question and then a source projection conditional on it, using that projection only if the child is selected. For each child \(C\) of \(D_i\), independently let \(P_C\) be its projection flag, with \(\Pr(P_C=1)=\beta_i=n_i^{-2/3}\). Write \(\boldsymbol e_C\) for the tuple of source edge records at its leaves and \(m_i\) for the number of those leaves. Thus \(\boldsymbol e_C\) has distribution \(\mu^{\otimes m_i}\).

Generate cut call \(q\in[T_i^{\mathrm{cl}}]\) by taking, independently for all \(q,C\), a uniform latent summand \[U_{q,C}\in H_C(O)^2, \qquad U_q=\sum_{C\text{ child of }D_i}U_{q,C}.\] The sum is uniform in \(H_i'\) because the addition map from the product of the child square spaces onto \(H_i'\) is a surjective linear map. Its fibers all have the same size. The resulting calls are independent, and are independent of the uniform arrays at every nonleaf proper descendant of \(D_i\). The first \(\ell_i\) calls can therefore serve as the rows of \(S\), with the rest substituted in the stopped ancestor expressions. This is exactly the modified sampling law on the visible arrays. No direct-sum assumption on the child spaces is involved.

Call \(C\) clean if \(P_C=1\), every \(U_{q,C}\) is zero, and every sampled array at a nonleaf node in the subtree rooted at \(C\) is zero. Write \(\mathcal C\) for the set of clean children.

Reconstructing the original local strategies

The preceding lemma leaves independent source questions, but repetition also requires local answer rules on those questions. Here the input restriction is substantive: the left decoder in Proposition 27 never receives \(a_i\), while the right decoder receives \(S\) only modulo \(a_i\). We now reconstruct precisely those inputs after the final exposure.

The vanishing upper bound

We can now bound low-rank agreement in the original modified law. All public exposures used for this purpose have already been specified, and none includes a useful-advice event, a slice event, a decoder output or a successful character match.

For the decoders supplied by Proposition 27, Proposition 30 gives \(\Pr(\mathcal L_{i,j,s})\ge\gamma_j/2\). Once the source power and the lower branching numbers have been fixed, \(p_{0,i}>0\) is already fixed independently of \(n_i\) and of higher branching. Taking, for example, \[n_i^{1/3}>\frac{64}{p_{0,i}}\log\frac{4}{\gamma_j}\] makes Equation (82) smaller than \(\gamma_j/4\), a contradiction. There are only finitely many choices of \(j>i\), so one branching number at level \(i\) accommodates all of them. Enlarging a higher branching number adds only exterior data and changes the deterministic stopped expressions; it changes neither the number of calls in Equation (79) nor the projected child dimensions in Equation (80). This is the uniform contradiction needed for the parameter selection in Section 8.

Row counts, rank cutoffs, and source repetition

Fix \(\delta\in\mathbb Q\cap(0,1)\) and put \(\varepsilon=\delta/3\). Choose a depth \(d\) with \(d\varepsilon\ge4\). The pair-counting argument of Section 5 allows a common positive simultaneous-success threshold; for definiteness take \[c=\varepsilon^2/2,\qquad \kappa=c/2,\qquad \eta=c^2/32.\] The losses below will be small enough for these choices. Apply Theorem 9 at the upper inverse threshold \(\eta/2\), and denote its density, number of constraints and minimum row count by \(\alpha,r,\ell_0\). Set \(\rho=\kappa\alpha/4\).

Choose the row counts from the root downwards. When choosing \(\ell_j\), all agreement constants \(\gamma_k\) with \(k>j\) have already been fixed. For every such \(k\), apply the lower analysis of Section 6 with agreement threshold \(\gamma_k\): fix its inverse constants, then a cross-matrix size, then a rank cutoff. Choose \(\ell_j\) large enough for each of these finitely many lower row requirements, and also so that \[ \ell_j\ge\ell_0,\qquad 2^{-(\ell_j-r)}<\rho/8. \tag{84}\] At the top level there are no preceding lower-test requirements.

With \(\ell_j\) fixed, the following conservative constants from Section 5 are available: \[\begin{align*} h_j&=2^{-r\ell_j}, &g_j&=\frac{\eta^2}{4}\,2^{-r\ell_j}, &q_j&=g_jh_j, \tag{85}\\ b_j&=\kappa\alpha q_j/4, &\tau_j&=\rho h_j/4, &\gamma_j&=b_j\,2^{-\ell_j-r}\tau_j^2/2. \tag{86}\end{align*}\] Choose \[ \lambda_j\le\min\{h_j/2,\tau_j^2/2\},\qquad (7/8)^{R_j}\le\lambda_j, \tag{87}\] and require every \(R_j\) to exceed the absolute minimum giving the quarter-balance premise in Lemma 23. The scalar induction uses only this lower balance minimum, not a lower level’s eventual accuracy \(\lambda_i\). Thus choosing \(R_j\) creates no requirement to determine a lower source dimension or a lower row count first.

Carry this procedure down to level \(1\). Take \(s\ge1\) to be the maximum of all the resulting rank cutoffs. Increasing a cutoff only strengthens the high-rank exclusion estimate, so the estimates for every pair \(i<j\) remain valid. With \(s\) fixed, choose the source repetition power \(t\) so that \[ \mathop{\mathrm{val}}(G_{\mathrm{src}})<\frac1{2s^2} \tag{88}\] on unsatisfiable inputs. Theorem 5 and the fixed source gap permit this choice. The parameter \(t\) fixes the source alphabets.

The absence of dimension and range factors in Theorem 9, Lemma 8, and the heavy-list bound is essential here. Although \(t\) changes the dimensions of all actual function spaces, it changes none of the already selected lower bounds in (86). Thus the source alphabet can be chosen after all row counts and rank cutoffs, leaving only branching to be determined.

Choosing the branching numbers

It remains to choose the branching numbers \(n_1,\ldots,n_d\). Take them to be integer cubes greater than one, so \(\beta_p=n_p^{-2/3}\) is rational. All row counts, product counts, source alphabets, inverse densities, rank cutoffs and agreement thresholds have already been fixed.

There are finitely many cuts, pairs of levels and extra-call variants. Fix a positive accuracy smaller than one tenth of every tolerance needed for the following uses:

1. transferring the original pair success to the modified lower-cut law;

2. preserving positive upper defined equality before the inverse step;

3. the row-fiber transfer in Lemma 25, with error at most \(\alpha q_j/16\);

4. the lower full-law comparison, with error at most \(\gamma_j^2/64\).

In (i) one may reserve error less than \(\varepsilon^2/4\), and in (ii) less than \(c^2/16\). The comparison from the modified \(i\)-law to the unrestricted \(j\)-law is a triangle of at most three raw comparisons. The factor ten accommodates this triangle as well as the direct uses. Reserve separately posterior discrepancy less than \(\gamma_j^2/64\) for every lower test, and require the clean-game upper bound to be below \(\gamma_j/4\).

Choose \(n_p\) in ascending order of \(p\). At that moment, Lemmas 20–22 and Lemma 32 provide a finite likelihood bound \(L_p\) and a positive clean zero-probability lower bound \(p_{0,p}\). They depend on already chosen lower branching and fixed parameters, but not on \(n_p\) or higher branching. As \(n_p\) tends to infinity through cubes, all of \[\begin{gather*} \frac{L_p}{\sqrt{n_p}},\qquad \sqrt{(1+n_p^{-4/3}L_p^2)^{n_p}-1},\qquad \frac{2n_p^{-2/3}L_p}{1-n_p^{-2/3}}, \tag{89}\\ (1-n_p^{-2/3}p_{0,p}/64)^{n_p} \tag{90}\end{gather*}\] tend to zero. Choose \(n_p\) to satisfy every relevant fixed tolerance. For (90), use the uniform bound conditional on exterior choices if those choices alter the zero probability.

Later higher branching cannot invalidate an earlier choice. The stopped-call representation in Section 4 bounds the number of raw calls into the \(p\)-cut using only the already fixed upper row and product counts. Higher branching introduces independent exterior functions and changes the deterministic map assembling ancestors; it does not change that raw block law or its number of calls. Total variation decreases under the assembly map, and the posterior estimate is proved on the raw lifted blocks before assembly. The clean event zeros a predetermined collection of those same calls. This proves the uniformity needed for the ascending choice.

Completing every fiber to size two

For fixed parameters, let \(L_{\max}\) and \(R_{\max}\) bound the numbers of legal answers at left and right vertices. These bounds are independent of the input length. Choose a common integer \(q\) with \[ q\ge\max\{2,R_{\max},\lceil1/\delta\rceil\}, \qquad 2q-L_{\max}\ge6/\delta. \tag{91}\] At each vertex, embed its legal answers in the common alphabet by a fixed ordering.

Consider one preliminary edge with legal projection \(\pi:L\to R\). For each \(b\in[q]\) its residual capacity is \[c_b=2-|\pi^{-1}(b)|\in\{0,1,2\},\] where a right label outside \(R\) has no legal preimage. The residual capacities sum to \(N=2q-|L|\). Enumerate all maps from the \(N\) illegal left labels into these capacities, giving each completion the same conditional weight. Together with \(\pi\), each such completion is a map \(\widehat\pi:[2q]\to[q]\) with every fiber of size exactly two. There are finitely many completions, and their number is a constant.

For any fixed illegal left label \(a\) and fixed right label \(b\), symmetry among the \(N\) illegal labels gives \[ \Pr_{\widehat\pi}[\widehat\pi(a)=b]=c_b/N\le2/N\le\delta/3. \tag{92}\] This bound is pointwise in the answers chosen by a labeling. Legal-left/illegal-right pairs never satisfy an edge. Given a labeling of the enlarged alphabets, retain all its legal answers and extend its other choices to arbitrary legal answers. Every edge satisfied with two legal answers remains satisfied by this legal extension. The weighted fraction of such edges is consequently at most the preliminary value. Equation (92) bounds all remaining accepting occurrences by \(\delta/3\) in total. Thus the completed weighted game’s value on an unsatisfiable input is at most \(\varepsilon+\delta/3\).

Every completion agrees with the original map on legal answers. A completeness labeling therefore satisfies every completed occurrence, not merely their average.

Explicit enumeration and removal of weights

We verify the deterministic running-time and encoding assertions. The source power \(t\), the number of tree leaves, every row count, and every local answer-domain size are constants. If the PCP instance has size \(N_{\mathrm{PCP}}\), all ordered outer question tuples can be enumerated in \(N_{\mathrm{PCP}}^C\) time for a fixed \(C\). Repeated question IDs remain separate coordinates, exactly as in the definition of the source game.

For each tuple, the local spaces can be constructed from their finite truth tables. Pointwise multiplication, linear algebra, supports, joint partitions and their canonical keys can all be found by exhaustive enumeration on constant-size domains. The recursively specified sampling law is likewise a finite enumeration of constant-size random choices. Question IDs require only polynomially many bits. After equal keys are identified, every vertex and every projection table can therefore be listed explicitly in polynomial time.

The preliminary probabilities are rational. Uniform finite-space choices have constant denominators, and source-question probabilities have polynomial bit complexity. Completions introduce only another constant denominator. Hence we obtain a polynomial list of positive-weight edge entries \(e_1,\ldots,e_m\), with rational weights \(w_a\) summing to one and with polynomial bit complexity.

In this fixed enumeration of positive-weight entries, set \(K=\lceil3m/\delta\rceil\) and \(k_a=\lfloor Kw_a\rfloor\). Add one to each of the first \(K-\sum_a k_a\) entries. The remainder is an integer in \([0,m)\), so this adds at most one copy to any entry and is a deterministic rule. Then \(\sum_a k_a=K\) and every copy lies in the original positive support. Some original occurrences may receive zero copies; no new support is added. Moreover, \[\mathop{\mathrm{TV}}\bigl((w_a)_{a=1}^m,(k_a/K)_{a=1}^m\bigr) \le m/K\le\delta/3.\] Output \(k_a\) copies of entry \(e_a\), with its already explicit exact-two table. The output is nonempty. Since \(K<3m/\delta+1=O(m)\) for fixed \(\delta\), polynomial-bit rational arithmetic and writing the \(K\) explicit copies both take polynomial time. For every labeling its acceptance probability changes by at most the total variation distance. Completeness remains one because only accepting support edges were retained. Soundness is at most \[\varepsilon+\delta/3+\delta/3=\delta.\]

Any syntactically trivial instance certified during preprocessing may be handled by fixed games with the same common alphabets. A single exact-two edge is a satisfiable game. For a fixed unsatisfiable output, take one vertex on each side and enumerate all exact-two maps uniformly as parallel occurrences. For any fixed pair of answers, the accepting fraction is \(1/q\le\delta\), by symmetry of the right labels. This also ensures the nonempty-output convention in every degenerate preprocessing case.

All constants chosen above can be hardcoded into one deterministic machine for the fixed rational \(\delta\). Theorem 1 requires no efficient dependence on \(\delta\). Together with Proposition 36, the completion and rounding arguments prove Theorem 1.