Perfect completeness for 2-to-1 games

1 Introduction

A projection game consists of a finite bipartite multigraph with disjoint vertex sets U,V, a nonempty multiset E of edge occurrences, finite answer sets at its vertices, and a map \pi_e from the left answer set to the right answer set for each occurrence e=(u,v). A labeling chooses one answer at each vertex and satisfies e when the right answer equals the image of the left answer under \pi_e. The value of the game is the maximum fraction of satisfied occurrences. Parallel occurrences may have different projection maps.

A 2-to-1 game has a common left alphabet [2q] and right alphabet [q], where [m]=\{1,\ldots,m\}, and

Khot introduced the games conjectures in the study of hardness of approximation [19]. His original formulation allowed fibers of size at most two; we use the exact-two convention. The 2-to-1 Games Conjecture asks for NP-hardness of distinguishing satisfiable games from games of arbitrarily small fixed value. The satisfiable case is the perfect-completeness requirement: one labeling must satisfy every constraint. Completeness 1-\eps for each fixed \eps>0 does not itself give this endpoint, since those reductions need not produce any finite satisfiable game. There is also an obstruction to amplifying a constant gap by ordinary repetition: repeating an exact-two projection k times gives 2^k preimages of every right answer. We prove the conjecture while retaining two-element fibers, in the following explicit form.

The theorem supplies the hypothesis of several perfect-completeness reductions. We derive consequences for maximum k-colorable subgraph and satisfiable Not-Two constraints below, identifying those already known unconditionally.

1.1 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+\eps [3, 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 [21]; Dinur, Khot, Kindler, Minzer and Safra developed the reduction to a Grassmann agreement hypothesis and the associated expansion problem [9, 10]. Barak, Kothari and Steurer related the agreement problem to expansion through the shortcode viewpoint [4]. The near-perfect expansion theorem of Khot, Minzer and Safra completed these ingredients, giving completeness arbitrarily close to one and arbitrarily small soundness [20]. More recently, Fei, Minzer and Wang proved perfect-completeness hardness for 4-to-1 games at arbitrarily small fixed soundness [12, 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 [6, Definition 5]. No such condition is part of Theorem 1.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 [7, 11, 20]. From the last input we derive the inverse shortcode estimates using the chart and averaging arguments of Barak, Kothari and Steurer [4]; Section 2 gives the forms needed here. The sampling comparisons have antecedents in the sub-code covering framework of Khot and Safra [22]. The passage from agreement of restricted bilinear forms to a fixed form of bounded rank has a close counterpart in Fei, Minzer and Wang [12, Lemmas 5.15–5.16]. We prove the comparisons needed for the function spaces and sampling laws below.

1.2 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 2.6 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

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 5.3). 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 7.2 and 7.3). 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.

1.3 Applications

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

Corollary 1.3 also follows by applying the O’Donnell–Wu reduction to Fei, Minzer and Wang’s perfect 4-to-1 theorem [12].

Through Guruswami and Sandeep’s reduction at d=2 [15, Theorem 1], Theorem 1.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 [12, Corollary 1.7]; the companion [26, Theorem 1.1] separately proves stronger independent-set soundness with three-colorable completeness.

2 Source games and inverse matrix structure

This section supplies the three external ingredients of the reduction and the precise matrix consequence that we will use. A perfect-completeness PCP and parallel repetition give a source game of arbitrarily small constant value. Grassmann expansion gives a dense constant-value slice of a matrix table that often agrees across a rank-one step. We prove the extensions needed for tables with arbitrarily many possible values, for small column spaces, and for finding a slice by random row advice.

Throughout, \F denotes the field with two elements. All vector spaces are finite-dimensional over \F, and all unspecified uniform distributions are on finite sets. For probability measures \mu,\nu on a common finite set, write \TV(\mu,\nu)=\frac12\sum_x|\mu(x)-\nu(x)|; in particular, every event has probabilities differing by at most \TV(\mu,\nu).

2.1 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

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 \val(G^{\otimes0})=1.

Raz proved exponential decay under parallel repetition for general two-player games [28]; Holenstein simplified that proof [18], and Rao obtained an alphabet-independent bound for projection games [27]. The precise estimate above is the parallel repetition theorem of Dinur and Steurer [11, 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\F^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 \F; and the projection selects the hth 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

For any required constant \sigma>0, choose a fixed integer t with (1-\gamma_0^2/144)^t\leq\sigma and take

Theorem 2.2 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 \F^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.

2.2 Matrix slices and the Grassmann input

Let H be a finite vector space, put K=\F^\ell, and identify K\otimes H with \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\F^a, the notation AM denotes its a specified combinations of rows. A row and column slice is a nonempty affine set

where U\in\F^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

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 [20], 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=\F^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 [4, Section 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.

2.3 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 2.5, so no functional outside this annihilator is introduced.

3 The tree of function spaces and the one-bit test

We first construct questions whose labels are nonempty parts of a joint-evaluation partition. Deleting one output direction gives maps with fibers of size at most two, and a satisfying source assignment supplies labels that satisfy every such map. We then specify the distribution of tests, obtaining a finite weighted game with perfect completeness. Its soundness will be proved in the next four sections; the conversion to the exact alphabets and unweighted format of Theorem 1.1 is deferred to Section 8. The shared questions must forget both the names of their output values and every input coordinate that their evaluations cannot distinguish. We give this identification explicitly, since it is responsible for both exact folding and the later comparison of clause and variable questions.

3.1 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

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 \F^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=\F^{\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 \F, tagged with the selected variable ID. Write \Omega_D(O) and \Omega(O) for the resulting products. The selected coordinate maps give a surjection

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 (3.1) form a direct sum is intended. In particular their copies of the constant function coincide.

3.2 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

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 (3.3) by the quotient map K_p\to K_p/\Span\{a\} at the D block and by the identity at every other block. Define

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 (3.3) and (3.4). 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,

Thus one fixed position j must work for the whole joint function, for all choices of the other arguments.

The global quantifier in (3.5) cannot be replaced by a sectionwise choice of position. For example, on \Omega_c\times\F 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 \F. 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

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 (3.6) 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

This is a bijection from legal labels to \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 3.4.

3.3 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:

The argument of the inverse belongs to \im g, since \operatorname{out}_f(P)\in\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.

3.4 Algebraic identities forced by joint answers

Evaluation tables and folding are standard mechanisms in PCP constructions; see Bellare, Goldreich and Sudan [5, Section 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 3.8 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.

3.5 The distribution of tests

The low-rank, Hadamard-bucket viewpoint is inspired by Golowich’s construction [14], as mediated by Fei–Minzer–Wang [12]. 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:

Return

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 (3.1), 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

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 (3.3) 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

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 (3.8). 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 3.6, the game has perfect completeness. The remaining sections prove its soundness by analyzing what a successful labeling reveals about the sampled arrays.

4 Changing the sampling law without revealing the path

The decoding argument will use uniform matrices at two different levels. Here we prove the distributional comparisons that permit those changes. There are two distinct conclusions: a total-variation comparison of the displayed functions, and a posterior bound for a child selected after inspecting those functions. Neither conclusion permits disclosure of the hidden path or of the projection mask. All statements below hold conditional on the complete original question tuple E; consequently they also hold after averaging over E, uniformly in the size of the source instance. We first replace the recursive draws at a cut by uniform draws, then compare that law with one in which a sparse set of children is projected. Each comparison retains only the observation specified in its lemma.

For probability measures on a finite set, use

when Q\ll P. Cauchy–Schwarz gives \TV(P,Q)\le\tfrac12\sqrt{\chi^2(Q\Vert P)}. An observation formed by a deterministic map cannot increase total variation: its discrepancy on an event is the discrepancy on that event’s inverse image. The same assertion holds on adjoining independent randomness and applying a randomized map, by conditioning on that randomness. These elementary facts will let us retain complete assembled queries without treating their components as independent.

4.1 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

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.

4.2 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:

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

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,

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

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.

4.3 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 [22, Section 3.4], with advice-conditioned thinning estimates in Dinur, Khot, Kindler, Minzer and Safra [9, Lemma 5.5, full version] and Fei, Minzer and Wang [12, 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.

Common observations in the three comparisons. The laws just defined serve different purposes, and each comparison forgets different information:

Original to unrestricted at one cut.

Lemma 4.2 replaces the cut draws and descendant arrays by uniforms after forgetting the path below that cut. The observation may include the ancestors reconstructed from those draws.

Modified to unrestricted at the lower cut.

Lemma 4.3 compares lifted functions on E after forgetting O, the projection choices, and the marks. Raw child contributions and all displayed descendant arrays may be retained.

Modified lower cut to unrestricted upper cut.

For j>i, Equation (4.9) applies to a common function of the upper-cut record specified in Lemma 4.3. That record retains pending scalar values there, but not their internal decompositions, and all displayed descendant arrays. The observation cannot select among those arrays using the hidden path.

The sparse product calculation also gives a posterior bound for a child selected after seeing the lifted matrices. This is stronger than a bound for a child fixed in advance, and will allow the lower decoder to choose a witness from its observed data.

The distinction from success conditioning is substantive: after the unconditional bad-event probability is bounded, it may be subtracted from any success probability. The posterior estimate itself need not hold within that success event. Exposing a direction a_i to the analyst does not provide it to the left strategy. Likewise, adding assembled ancestor values to the lifted blocks changes no information, because they are functions of those blocks and \Xi_i; treating those values as independently sampled exterior data would not justify the product law used above.

4.4 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 [24]; 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 \Prob_{x\sim\mu}(f(x)=b)\ge1/4 for both b\in\F.

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

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.

5 Two successful levels and upper decoding

We show that appreciable test acceptance produces two local bilinear-form decoders. Their outputs agree on the projected lower space with a probability depending only on the upper row count. The left output is always a normalized product form whose restriction to its displayed lower rows has rank at most one. Keeping this probability independent of the lower row count will allow us to choose that count afterward.

Fix a legal labeling of the partition vertices, extended to unused legal keys as in Section 3. All responses below are evaluations restored from this fixed labeling. For a candidate test at level p, write \mathrm{Acc}_p for its acceptance event. Sample the directions for all candidate tests independently, using the same left query and sampled path.

5.1 Selecting two levels and a quotient table

Suppose that the labeling accepts with probability at least \eps, where 0<\eps<1, and choose d\eps\ge4. If N=\sum_{p=1}^d\one_{\mathrm{Acc}_p}, then

Consequently some i<j satisfies

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 \Prob_i for this law, with all functions also pulled back to the original tuple E. By Lemmas 4.2 and 4.3, we can require the comparison error in (5.1) to be at most \eps^2/4. Thus, throughout this section,

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=\F^{\ell}, \ell=\ell_j, and M=M_{D_j}. The data

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

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

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 3.7 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 (5.3).

Define a usefulness mark by

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 \Prob_i and use exactly the same partial tables under all subsequent laws.

5.2 From row advice to a predictable upper response

Write \Prob_j^0 for the unrestricted cut law in the last assertion of Lemma 5.1, 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 2.7 at equality threshold \eta, obtained from Theorem 2.6 at threshold \eta/2. Assume that \ell meets their largeness requirement.

Sample A\in\Hom(K,\F^r) uniformly and independently. For any (P,A,C), where C\in\F^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

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 \Prob_j^0 is at least

Indeed, the set of qualifying P has mass at least \eta, and for each such P Lemma 2.7 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=\Span\{q_1,\ldots,q_k\}\subseteq\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

This uses the direct-sum decomposition H=B\oplus s(H/B). At every match to the selected response the restored upper output equals

Every z\in z_0+Z satisfies

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):

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 (5.8). For uniform M in a fixed nonempty row fiber, imposing k columns costs at most k\ell\le r\ell binary equations. Therefore, with

the reference law satisfies

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.

5.3 The local inputs and the original hidden law

Here and below the experiment is \Prob_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

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

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

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 (5.14), 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

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 (5.13) 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 (5.16) 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

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 4.5, and that

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

5.4 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 [13]. We prove the needed statement for the present nonuniform, own-question law; no efficient decoding algorithm is required. If V=W\otimes H', write

For \sigma\in K^* and a fixed function G:V\longrightarrow K, put g_\sigma(X)=(-1)^{\sigma(G(X))}.

5.5 Constructing the two decoders

The algorithms in Proposition 5.4 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.

6 From tested rank to full rank

Proposition 5.4 provides two local decoders whose bilinear forms agree after projection with probability at least \gamma_j>0. The left form has rank at most one on the displayed lower rows. We now show that a positive part of this agreement comes from left forms of bounded rank on the entire lower function space. The distinction matters: the form selected by the decoder can depend on the rows on which it is tested.

The passage from agreement of restricted forms to a fixed form of bounded rank has a close predecessor in Fei, Minzer and Wang [12, Lemmas 5.15–5.16]. Here we carry it out for the tree function spaces, using the sparse-projection posterior bound and an estimate on affine row and column slices.

Fix the levels i<j, and write

All restrictions below use the injective pullback identifying H_i' with a subspace of H_i. For a bilinear form F on H_i, let

Call F admissible at S if there is a linear functional z\in(H_i^2)^* such that

The left form in Proposition 5.4 is admissible: its functional on H_{D_j}(E) restricts to H_i^2, since D_i is a proper descendant of D_j. On a default input a legal point evaluation has the same properties. Admissibility is a condition on the left input and output alone; in these finite spaces it can also be checked by solving the linear equations for z and computing a matrix rank.

6.1 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 4.1, with the independent cut rows in the modified experiment defined before Lemma 4.3. 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 (4.3) 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.

6.2 A rank bound on affine slices

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

7 Clean children and independent repetition

A normalized product form of bounded rank determines a short odd list of answers at each source leaf. When the decoded forms agree after projection, their lists satisfy a projection constraint. To apply parallel repetition to these lists, we must recover independent source edges and local answer rules despite their sampled advice.

We do this by finding projected children whose contributions to every sampled function are zero. The probability of this event is exactly independent of their source questions. Revealing the remaining data therefore leaves independent source edges at designated leaves, and each player can reconstruct its original decoder input from its own questions there. Repetition then bounds the low-rank agreement from Proposition 6.3.

Fix levels i<j and use the modified experiment at D_i throughout this section. Write

We identify H_i' with its pullback subspace of H_i. The integer s\ge1 is a full-rank cutoff as in Proposition 6.3. The source game, denoted by G_{\mathrm{src}}, is a fixed t-fold power of the clause–variable game. For a source question u on the left and v on the right, write \Lambda_u and \Gamma_v for their nonempty legal answer sets. Thus \Gamma_v=\F^t, with a separate coordinate for each slot, including slots with repeated variable IDs. Let \mu be the distribution on source edge records e=(u,v,\pi_e).

7.1 Odd lists and leaf indicators

For a finite nonempty set \Lambda, define

Given a map \pi:\Lambda\to\Gamma, define its parity pushforward by

The same parity pushforward describes restriction of Fourier characters in low-degree long-code analysis [8, Section 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 [23, 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 7.1 identifies their outputs whenever normalized low-rank agreement occurs.

7.2 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 [21, Sections 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 (4.3), its size is

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

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.

7.3 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 5.4 never receives a_i, while the right decoder receives S only modulo a_i. We now reconstruct precisely those inputs after the final exposure.

7.4 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 5.4, Proposition 6.3 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,

makes Equation (7.7) 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 (7.4) nor the projected child dimensions in Equation (7.5). This is the uniform contradiction needed for the parameter selection in Section 8.

8 Choosing the parameters and completing the reduction

We now combine the local statements into a reduction. The parameters are constants depending on the requested soundness, but their order of choice matters: the upper agreement guarantee and its constants must be fixed before the lower row counts used to test rank. We choose row counts from the root downwards, fix the source repetition power, and then choose branching numbers from the leaves upwards. The bounds used during these choices are uniform in every dimension and table range not yet fixed; the decoders themselves are instantiated after all choices. This establishes soundness for the preliminary weighted game. Completing its at-most-two maps and rounding its weights will give the fixed alphabets and explicit unweighted output of Theorem 1.1.

8.1 Row counts, rank cutoffs, and source repetition

Fix \delta\in\mathbb Q\cap(0,1) and put \eps=\delta/3. Choose a depth d with d\eps\ge4. The pair-counting argument of Section 5 allows a common positive simultaneous-success threshold; for definiteness take

The losses below will be small enough for these choices. Apply Theorem 2.6 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

At the top level there are no preceding lower-test requirements.

With \ell_j fixed, the following conservative constants from Section 5 are available:

Choose

and require every R_j to exceed the absolute minimum giving the quarter-balance premise in Lemma 4.5. 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

on unsatisfiable inputs. Theorem 2.2 and the fixed source gap permit this choice. The parameter t fixes the source alphabets.

The absence of dimension and range factors in Theorem 2.6, Lemma 2.5, 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 (8.3). Thus the source alphabet can be chosen after all row counts and rank cutoffs, leaving only branching to be determined.

8.2 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. (i)

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

2. (ii)

   preserving positive upper defined equality before the inverse step;

3. (iii)

   the row-fiber transfer in Lemma 5.2, with error at most \alpha q_j/16;

4. (iv)

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

In (i) one may reserve error less than \eps^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 4.2–4.4 and Lemma 7.2 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

tend to zero. Choose n_p to satisfy every relevant fixed tolerance. For (8.7), 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.

8.3 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

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

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

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 (8.9) bounds all remaining accepting occurrences by \delta/3 in total. Thus the completed weighted game’s value on an unsatisfiable input is at most \eps+\delta/3.

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

8.4 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,

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

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.1 requires no efficient dependence on \delta. Together with Proposition 8.1, the completion and rounding arguments prove Theorem 1.1.