Results on projection games, the reduction to 2-to-1 games and its soundness

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Randomness does not raise the value of a projection game — Lemma 1.1. If the players of a projection game use random numbers independent of the edge, their probability of winning is at most the value of the game.
• A gap for formulas with three different variables per clause — Proposition 3.1. Assuming a PCP theorem with perfect completeness for constraint systems of bounded arity: there are gamma_0 > 0 and a polynomial-time map to 3-CNF formulas with three different variables per clause that preserves satisfiability and makes every assignment violate a fraction gamma_0 of the clauses in the unsatisfiable case.
• The value of the clause-variable game — Lemma 4.1. For a 3-CNF formula Psi the clause-variable game has value 1 if Psi is satisfiable, and at most 1 - gamma/3 if every assignment violates a fraction gamma of the clauses.
• The base game: a projection game with perfect completeness and small soundness — Theorem 5.1. Assuming the PCP theorem with perfect completeness and parallel repetition for projection games: for every sigma > 0 a polynomial-time map from formulas to projection games with answer sets of sizes 7^t and 2^t, of value 1 for satisfiable formulas and at most sigma otherwise.
• Sets of matrices over F_2 that are often preserved by a rank-one step — Lemma 2.1. Assuming the expansion theorem for Grassmann graphs (GE): a set S of l x m matrices over F_2 with P(M + a h^T in S) >= eta for M uniform in S has density at least alpha in a slice with at most r row combinations and r column values; alpha, r depend only on eta (l and m large).
• Projection of a slice of matrices to a subset of the columns — Lemma 3.1. For a slice of matrices on H + D, its image on H is a slice with the same row combinations and at most as many column values, and all fibres of the projection have the same size.
• Inverse theorem for partial tables on matrices over F_2 — Theorem 4.1. Assuming (GE): if a partial table f on K tensor H satisfies P(f(M) = f(M + ah) defined) >= eta, some value fills a fraction alpha of a slice with at most r row combinations and r column values; alpha, r, l_0 depend only on eta, not on dim H or on the number of values.
• Many good row fibres — Lemma 4.2. Assuming (GE): under the hypothesis of the inverse theorem with eta, a uniform matrix lies in a good row fibre for some row map with probability at least eta/4, and for a uniform row map with probability at least (eta/4) 2^(-r l).
• The function spaces on the tree — Lemma 2.1. The spaces H_D (all functions at a leaf; at an inner node the sum of the spans of products of two functions of each child) contain 1, satisfy H_C^2 in H_D for every proper descendant C of D, and are preserved by the pull-back along the projections of the base game.
• Shared keys — Lemma 4.3. A function on the answers of a mixed family of base questions and its composition with the projection from the full family have the same key (the same typed reduced domain and partition) and the same restored values.
• Constraints of the new game have at most two preimages — Lemma 5.1. The constraint of (E, M, D, a), which forgets the component along a of the value at the node D, is a map from the labels of the left key onto the labels of the right key with at most two preimages of every label.
• Perfect completeness of the new game — Proposition 5.2. If the formula is satisfiable, one labeling of all keys satisfies every constraint, for all choices of the parameters; so every game supported on these constraints has value 1.
• Joint folding — Lemma 1.1. Adding to a row of the array at a node D a constant and products of rows of arrays at proper descendants keeps the key of the joint function, and for every label the restored value of that row changes by the same constant and the same products of restored values.
• The functional of a response on products of displayed rows — Lemma 2.1. For a label with restored values y_C there is exactly one functional on the span of 1 and of the products of the rows at given proper descendants with value 1 at 1 and (y_C)_u (y_C)_v at the products; every extension to H_D has the matrices y_C y_C^T, of rank at most one.
• Buckets and steps of rank one — Lemma 3.1. If the buckets h_v, v nonzero in K, are independent and uniform in H, then M = sum v tensor h_v is uniform in K tensor H, and resampling the bucket of a nonzero a replaces M by M + a tensor h with h uniform and independent of M and a.
• The game of the reduction before the completion of the alphabets — Proposition 4.1. The tests (base questions at the leaves, a random path with recursive samples, uniform arrays off the path, a constraint at a random level of the path) define a projection game with at most two preimages of every label and value 1 for a satisfiable formula.
• The calls that reach a node of the path — Lemma 2.1. The arrays at the path nodes of the levels d to p are fixed expressions in exterior uniform functions and in T_p = sum over k from p to d of b_k times the product of the c_h, p < h <= k, independent calls at D_p, where b_k = 2^(l_k) - 1 and c_h = 2 R_h; the count does not depend on the numbers of children.
• One hidden child — Proposition 3.1. Given the base questions, the path to D_p and the exterior data, the law of the blocks of the children of D_p (their contributions to the calls and the arrays in their subtrees) differs from the product of the uniform laws by at most (1/2) sqrt(L_p / n_p) in total variation, when the child on the path is not observed.
• Sparse projection — Proposition 4.1. If each child of D_i is marked independently with probability beta and the blocks of the marked children are uniform in the spaces of the projected questions, the law of the blocks, without the marks, differs from the product of the uniform laws by at most (1/2) sqrt((1 + beta^2 L_i)^(n_i) - 1) in total variation.
• The posterior bound — Proposition 4.2. Under the modified law, given all blocks and independent data, every child is marked with a conditional probability of at most beta L_i / (1 - beta); a set of at most m children chosen from these data contains a marked child with probability at most m beta L_i / (1 - beta); two different bilinear forms computed from these data agree on the projected space with probability at most 2 beta L_i / (1 - beta).
• The comparison at two levels — Proposition 4.3. For i < j, the exterior data at D_j, the calls at D_j and the arrays below D_j, generated with the modified law at a random node of the level i below D_j, differ from the unrestricted law at D_j by at most the sum of the bound of Proposition 3.1 at the levels j and i and the bound of Proposition 4.1 at the level i.
• Bias of the samples — Proposition 5.1. If R_k >= 6 for all k, every nonzero linear functional has a bias of at most (7/8)^(R_p) on a call at the path node D_p, the law of every call is quarter-balanced, and every nonzero functional on W tensor H has a bias of at most (7/8)^(R_j) on the sum of v tensor h_v over the nonzero v in W with independent calls h_v at D_j.
• Two accepted levels — Lemma 1.1. If a labeling satisfies the test with probability at least epsilon and d epsilon >= 4, there are levels i < j at which the constraints with independent directions are satisfied together with probability at least 3 epsilon^2 / 4.
• The response at a matrix from the response table — Lemma 3.1. If the table value at the class of M modulo B is (y^, (y_C)), the label at the left key of the family with M at D_j has the restored values y_C at the nodes of the level i below D_j and y^ + (M - s(pi M)) b_y at D_j, where b_y is the functional of the response.
• Equality along the replacement of one bucket — Lemma 4.1. Under the modified law, if both levels are accepted with probability at least c, the partial table has equal defined values at the classes of M and of M with the bucket of the direction a_j replaced, with probability at least c^2/8.
• Equality along the uniform step — Proposition 4.2. Under the unrestricted law at the level j the matrix M is uniform and independent of the background, the replacement of a bucket is the uniform step of rank one, and the partial tables have equal defined values along the step with probability at least c^2/8 minus the comparison error.
• The functionals of a good advice — Lemma 5.2. For a good advice with the value t_* = (y^*, (y*_C)): at every M whose table value is t_*, the restored value at D_j is M z_0 + y^*; every z in z_0 + Z has z(1) = 1 and z((M_C)_u (M_C)_v) = (y*_C)_u (y*_C)_v for every node C of the level i below D_j.
• The events I and J — Lemma 5.3. Under the unrestricted law, the event J (good advice and the column values of the witness) has probability at least g_0 = (eta^2/4) 2^(-2 r l), and the event I (J and the table value t_*) has probability at least alpha times that of J.
• The prediction of the upper response — Proposition 6.1. Under the modified law, P(J and the upper value of the right answer at the level i equals M z_0 + y^*) - rho P(J) >= b_0, with rho = kappa alpha / 4 and b_0 = kappa alpha g_0 / 4, if the comparison error is at most alpha g_0 / 16.
• The law of the hidden part of the upper matrix — Lemma 1.1. Under the modified law, given the data of both sides, the buckets of the upper matrix with index in the kernel W of the row map are independent calls; the law of their sum X depends only on the projected questions, the path and W; every nonzero functional has bias at most (7/8)^(R_j) under it; and the upper value of the right answer at the level i is G(X).
• The list of heavy characters — Lemma 2.1. For a law mu on W tensor H' with all nonzero characters of bias at most lambda <= min(h_0/2, tau^2/2), a function G with values in K and 2^-(l-r) < rho/8: each list of characters with correlation at least tau = rho h_0/4 with (-1)^(sigma G) has at most 2/tau^2 elements; a slice given by at most r column values has mass at least h_0/2; and if G(X) = X z' + k_0 with conditional probability at least rho on the slice, some sigma not vanishing on W has a list element in (sigma|W) tensor z' + W* tensor Q.
• The two decoders of the upper level — Proposition 3.1. For a labeling that satisfies the test with probability at least epsilon there are a bilinear form F_L computed from the left data and a bilinear form F_R computed from the right data that agree on the projected space with probability at least gamma_j = b_0 2^-l (tau^2/2) 2^-r; F_L(x,y) = z(xy) with z(1) = 1, and its matrix on the rows of the array at D_i has rank at most one.
• Agreement with forms of bounded rank — Proposition 1.1. If the two decoders agree on the projected space with probability at least gamma, then for suitable m, s and l_i that depend only on gamma, and for a large number of children at the level i, they agree with a left form of rank at most s on H_i with probability at least gamma/2.
• Equality of the left table along a step of the lower array — Proposition 3.3. With decoders without random choices and the left forms of rank at most s removed: under the unrestricted law at the level i the lower array S, the direction a and the function l are uniform and independent, and the table has equal defined values at S and S + a tensor l with probability at least h^2 - 2 beta L/(1 - beta) - upsilon, where h is the agreement probability of the table with the right form.
• A fixed form on a slice — Lemma 4.1. For a bilinear form F on H, l >= 2m + r' and S uniform in a slice of K tensor H with at most r' row combinations and r' column values: P(rank Gram_F(S) <= 1) <= (2^m - 1) 2^(-(rank F - 2r')) + (1 + (2^m - 1)^2) 2^(-m^2).
• The game on odd lists — Lemma 1.1. The parity map of a map pi sends lists with an odd number of at most s elements to such lists; the game on lists of a projection game G is a projection game of value at most s^2 val(G).
• The lists of a form — Lemma 2.1. For F(x,y) = z(xy) with z(1) = 1 and rank at most s, the set of answers a at a leaf with F(e_a, e_a) = 1 has an odd number of at most s elements; if a form on the projected space agrees with F there, its list at a replaced leaf is the parity image of the list of F.
• Clean children and the law of their edges — Lemma 3.1. Under the modified law, given the exterior, the children of D_i are clean independently with the probability beta p_0, where p_0 does not depend on the questions; given the public data, the base edges at the designated leaves of the clean children are independent with the law of the base game.
• The data of the decoders from public data and own questions — Lemma 4.1. Given the public data, the left data are a function of the public data and the left questions at the designated leaves of the clean children, the right data of the public data and the right questions there, and all arrays and buckets do not depend on the arguments below clean children.
• The bound for the agreement with forms of bounded rank — Proposition 5.1. If the base game has a value below 1/(2 s^2), the probability under the modified law that the two decoders agree on the projected space with a left form of rank at most s is at most (1 - beta p_0/64)^(n_i) <= exp(-p_0 n_i^(1/3)/64); this uses parallel repetition.
• The choice of the parameters — Proposition 2.1. Under the three hypotheses, for every epsilon there are parameters t, d, n_p, l_p, R_p that satisfy all the conditions of the proof of soundness for all pairs of levels: rows from the root downwards, then the number of repetitions, then the numbers of children from the leaves upwards.
• Soundness of the game of the reduction — Theorem 3.1. Under (GE) and (PR), if the parameters satisfy the conditions and the base game of a 3-formula has a value below 1/(2 s^2), the game of the reduction for this formula has a value below epsilon.
• Completion to maps that are exactly 2-to-1 — Proposition 4.1. A projection game with at most two preimages of every answer and bounded answer sets is completed to a weighted 2-to-1 game with the answer sets {1..2q} and {1..q}; a labeling that satisfies all edges still does, and the value grows by at most delta/3 if 2q - L_max >= 6/delta.
• Equal weights — Proposition 5.1. Replacing M edges with rational probabilities w_a by k_a copies with the uniform law on K = ceil(3M/delta) copies, k_a the rounding of K w_a, changes the winning probability of every labeling by at most delta/3.
• The size of the game — Proposition 5.2. For fixed parameters, the list of the tests of positive probability of the game of the reduction for a 3-formula, with keys, maps and rational probabilities, is computed in polynomial time; the label sets have at most 7^(t n) elements, n the number of leaves.
• The 2-to-1 games theorem with perfect completeness — Theorem 6.1. Assume (PCP), (PR) and (GE). For every rational delta in (0,1) there are q >= 2 and a polynomial-time map from formulas in conjunctive normal form with three literals per clause to 2-to-1 games with the answer sets {1..2q} and {1..q} and the uniform law on a list of edges, with value 1 for a satisfiable formula and value at most delta otherwise.

Reading order

Ten lessons: projection games and the base game, proved from two named hypotheses (a PCP theorem with perfect completeness and parallel repetition); the inverse theorem for tables on matrices over the field with two elements, proved from a third named hypothesis (expansion of Grassmann graphs); the construction of the new game, with constraints that have at most two preimages and with perfect completeness; the exact relations of its labelings with the law of its tests; the comparisons of this law with uniform laws, the first step of the proof of soundness; the upper decoding step, from two accepted levels to two decoders whose bilinear forms agree with a fixed probability; the step from the rank on the tested rows to a bounded rank on the whole lower space; the upper bound for this agreement by clean children and parallel repetition; and the choice of the parameters, the completion to maps that are exactly 2-to-1, and the theorem. The theorem on 2-to-1 games with perfect completeness is proved in the course from the three named hypotheses; these three are not proved here.