Compose the PCP theorem with parallel repetition (Label Cover) and a long-code test. Its soundness analysis is Fourier analysis with noise, extending the BLR argument. First step: define \(\mathsf{PCP}_{c,s}\) with explicit rational \(c\) and \(s\), show it agrees with the existing \(\mathsf{PCP}\) at \(c = 1\), \(s = 1/2\), and define gap-preserving reductions between constraint satisfaction problems.

The NW generator built from \(L\) on a design with logarithmic seed is a pseudorandom generator by the hybrid and reconstruction argument. Enumerate its \(\mathrm{poly}(n)\) seeds. First step: prove that designs with the required parameters exist, then restate the existing finite reconstruction against circuit tests instead of Kolmogorov tests.

Amplify worst-case hardness to the average-case hardness required by Nisan–Wigderson, via local list decoding of a concatenated code or the XOR lemma. First step: instantiate the abstract list-decodable code interface Complexity.BooleanListCode, whose decoder reads the whole received word, with a concrete code, and add the local decoding this argument needs. An explicit list-decodable family is itself still planned (Theorem 1129).

Approximate the circuit by a low-degree polynomial in two ways: in \(L^2\) via Linial–Mansour–Nisan, and pointwise off a small error set via Razborov–Smolensky. Then sandwich it. First step: define \(k\)-wise independent distributions and \(\varepsilon \)-fooling for a finite family of tests.

Recursively apply pairwise-independent hash functions, halving the program at each level. The library’s fixed-width pairwise-independent hash families (Definition 210), built for Stockmeyer-style counting, are a starting point. First step: define read-once branching programs and \(\mathsf{BPL}\) as logspace probabilistic machines that halt in polynomial time. The library’s branching programs are width-\(w\) permutation programs, used at width \(5\) for Barrington’s theorem: each step applies a permutation of the \(w\) states selected by one input bit, so they are not required to be read-once, and their steps are permutations rather than arbitrary maps between layers.

Make the graph regular, then alternate powering with zig-zag products against a constant-size expander until the graph is an expander of logarithmic diameter. The resulting rotation maps are computable in logspace. The PCP development’s internal modules contain regular graphs presented by rotation maps, the zig-zag product of \(G\) and \(H\) with the spectral bound \(\lambda _G + \lambda _H + \lambda _H^2\) (the simpler Reingold–Vadhan–Wigderson estimate), and a zig-zag tower of expanders grown from one constant-size base graph, all of which may be reusable. They are not stated about space-bounded computation. First step: fix a graph encoding and state the undirected connectivity language.

A good predictor is a noisy oracle for the Hadamard encoding of \(x\). Local list decoding, which finds every large Fourier coefficient of the predictor, recovers a short list containing \(x\). First step: define hard-core predicates, and prove the finite list-decoding statement for the Hadamard code in Fourier language.

Evaluate the tree of generator applications along the input bits. A hybrid argument over tree levels, restricted to the nodes the adversary queries, bounds the advantage. First step: define cryptographic PRGs and a PRF oracle game with negligible advantage, compatible with the planned pseudorandom function families of the natural-proofs barrier (Definition 1083). Also prove that one-way permutations yield PRGs via Goldreich–Levin and the existing finite Yao hybrid step (Lemma 1142).

A \(c\)-bit protocol partitions \(X \times Y\) into at most \(2^c\) rectangles. Lindsey’s lemma bounds each rectangle’s bias using orthogonality of the Hadamard matrix, that is, of the parities. First step: prove the rectangle partition lemma and the fooling-set bound \(D(\mathrm{EQ}_n) \ge n\).

Both translations preserve depth and leaf count exactly. From a formula: an OR gate becomes an Alice node where she says whether her input satisfies the left disjunct, and play continues in a disjunct her input satisfies; an AND gate becomes a Bob node where he says whether his input satisfies the left conjunct, and play continues in a conjunct his input violates. A literal leaf names its coordinate, and a constant leaf, reachable only on an empty rectangle, names a default coordinate, which exists because \(n \ge 1\). From a protocol: track the rectangle of inputs consistent with the transcript. Alice nodes become OR gates, Bob nodes become AND gates, and a leaf naming \(i\) becomes whichever of \(x_i\) and \(\lnot x_i\) is \(1\) on Alice’s side and \(0\) on Bob’s side, or a constant when one side is empty.

Show the permanent is in \(\mathsf{VNP}\) via Ryser’s formula. For hardness, convert formulas to weighted graphs whose cycle covers compute the polynomial. First step: on top of the imported arithmetic circuits and their MvPolynomial semantics, define polynomial families, their size and degree bounds, and \(p\)-projections. The Boolean counterpart, \(\# \mathsf{P}\)-completeness of the \(0/1\) permanent, would connect to the existing class \(\# \mathsf{P}\) (Definition 198).

\(X \otimes Y \otimes Z\) maps outer products to outer products and is continuous, so it maps the closure of the rank-\(r\) tensors into itself.

Choose \(k\) independent rows, then \(k\) independent columns of the resulting \(k \times n\) matrix. The vanishing of all \((r+1)\)-minors is a closed condition.

For \(u \ne 0\) the map \(X \mapsto u \wedge X\) on \(\Lambda ^p A\) has rank \(\binom {\dim A - 1}{p}\): the composite of two such maps vanishes, and the rows \(K \cup \{ i_0\} \) and columns \(K\) with \(i_0 \notin K\) give an invertible diagonal submatrix when \(u_{i_0} \ne 0\). The flattening of \(u \otimes v \otimes w\) factors through this map, the flattening is linear in \(T\), and matrix rank is subadditive and lower semicontinuous.

In the sum, every term except the one with the least exponent \(E_0\) is divisible by \(2^{E_0 + 1}\). In the Leibniz expansion of \(\det M\), a permutation \(\sigma \) supported on the nonzero entries contributes \(\pm 2^{E(\sigma )}\) with \(E(\sigma ) = \sum _j 2^{L_{\sigma (j) j}}\), the binary number whose set bits are the labels used by \(\sigma \). These labels determine the pairs \((\sigma (j), j)\), so the exponents are pairwise distinct. A block-diagonal minor has determinant the product of the block determinants.

Compare each sum with \(|K|\, o_p\): the at most \(p\) elements of \(K\) above the median add at most \(p (o_{2p} - o_p)\), the at most \(p\) elements below it subtract at most \(p (o_p - o_0)\), and the sizes of two subsets differ by at most one. A sum over \(p\) elements lies in \([p\, o_0, p\, o_{2p}]\), so two such sums differ by at most \(pL\).

A nonzero entry in column \((I, j)\) and row \((J, \ell )\) of \(U_A^{\wedge p}\) has \(J = I \cup \{ t\} \), \(t \notin I\), and \(\ell = j + o_t\), so \(w = j - \sum _I o = \ell - \sum _J o\) is preserved. For each of the \(m - s\) shifts \(w\) with \(w + \sum _K o \in [0, m)\) for all subsets \(K\) of size \(p\) or \(p + 1\), take the columns \((I, w + \sum _I o)\) and the rows \((\sigma (I), w + \sum _{\sigma (I)} o)\), where \(\sigma \) is a bijection from \(p\)-subsets to \((p+1)\)-subsets with \(I \subseteq \sigma (I)\). It exists by Hall’s theorem, since the inclusion graph is \((p+1)\)-regular on both sides. The resulting minor is block diagonal. In each block, the entries are \(0\) or \(\pm 2^{2^{e}}\), the columns \(w + \sum _I o\) differ by at most the \(p\)-subset spread, so the label condition and distinct subset sums make the labels distinct, and \(\sigma \) is a perfect matching of the nonzero entries, so the block is nonsingular by Lemma 1383. The border-rank bounds follow from Theorem 1382 after projecting onto the \(2p + 1\) cluster slices, which sends \(T\) and each such \(T'\) to \(U\).

The minor on all the chosen rows and columns is block triangular, so its determinant is the product of the block determinants.

Index columns by positions \(j\) and rows by \(\ell \) in \([0, n)\). A single-cluster block of shift \(w\) (Theorem 1386) uses the columns \((I, w + \sum _I o)\) and the rows \((\sigma (I), w + \sum _{\sigma (I)} o)\). For offsets with median \(\rho \) and diameter \(L\) every sum \(\sum _K o\) lies within \(pL\) of \(|K| \rho \), so the columns of the block lie within \(pL\) of a center \(x\) and its rows within \(pL\) of \(x + \rho \). A positive column at \(x\) meets rows within \((2p + 1)L\) of \(x + r\) (through the positive slices) and of \(x - s\) (through the negative ones); a negative column meets rows near \(x - s\) and \(x + r\).

Take the blocks whose centers lie in four tiles, each shrunk by \(\mu = (p + 1)L\) at both ends and cut to fit in \([0, n)\): positive blocks with centers in \(P_1 = [0, s)\) and \(P_2 = [z, z + s)\), whose rows lie in \([r, z)\) and \([z + r, 2z)\), and negative blocks with centers in \(N_1 = [s, z)\) and \(N_2 = [z + s, 2z)\), whose rows lie in \([0, r)\) and \([z, z + r)\). The positive system (\(P_1 \cup P_2\)) and the negative system (\(N_1 \cup N_2\)) never meet. A positive column of \(P_1\) meets only its own block, one of \(P_2\) its own block and rows of \(P_1\) (shift \(-s\)); a negative column of \(N_2\) meets only its own block, one of \(N_1\) its own block and rows of \(N_2\) (shift \(+r\)); everything else falls outside the chosen rows, because tiles of opposite signs are \(2\mu {\gt} (2p + 1)L\) apart. In the order \(P_1 {\lt} P_2 {\lt} N_2 {\lt} N_1\) the minor is block triangular (Lemma 1387). Within one block the slices of the other cluster contribute nothing, since \(o^+_t \ne o^-_t\), so the diagonal block is a nonsingular single-cluster block; blocks of the same cluster with different shifts do not meet through that cluster, since the shift is preserved. Only labels within one diagonal block are compared: positions of one cluster, whose slices differ by at most \(L\) and whose columns differ by at most the \(p\)-subset spread, at most \(pL\). So labels that separate an \((L, pL)\) window suffice. The tiles have widths \(s\), \(\min (s, n - r - z)^+\), \(\min (r, n - s - z)^+\) and \(r\), each less \(2\mu \). When \(2z \le n\) both tiles fit and \(W = 2z\); when \(2z {\gt} n\) the second tile is cut by \(n\) and \(W \ge 2(n - z)\). The border-rank bounds follow from Theorem 1382 after the paired projection, which sends each such \(T'\) to \(V\).

The original sketch of this step built a tile of side \(z\) and repeated it in a square of side \(2z\), claiming that the interactions between the two copies run in one direction. For the partition into copies they do not; the decomposition above, which separates the positive and negative systems and orders each one, replaces that argument and needs no auxiliary square of side \(2z\).

The spread of each cluster is at most its \(|{\rm median}| + pL\) (Lemma 1385), so the single-cluster certificate gives the terms \(n - r\) and \(n - s\) with loss \(pL\); Theorem 1388 gives \(r + s\) and \(2 \min (r + s, n - r - s)\) with loss \(8(p + 1)L\). Finally \((p + 1) \binom {2p+1}{p} = (2p + 1) \binom {2p}{p}\).

Write \(T\) as a limit of \(T_n = \sum _{s=0}^{r} u_{n,s} \otimes v_{n,s} \otimes w_{n,s}\). A unit vector \(\hat u_n\) on the line of \(u_{n,0}\) makes \(\Pi _{\hat u_n}\) kill the first summand, so \((\Pi _{\hat u_n} \otimes 1 \otimes 1) T_n\) has rank at most \(r\). A subsequence of \(\hat u_n\) converges on the compact unit sphere to some \(u\), and \((u, S) \mapsto (\Pi _u \otimes 1 \otimes 1) S\) is continuous at \(u \ne 0\). If \(\ker P \subseteq \ker P'\), then \(P' = G P\) for a matrix \(G\), and \(G \otimes 1 \otimes 1\) does not increase border rank.

Let \(i_0\) minimize \(\tau _A\) on the support of \(u\) and \(\lambda (t) = \operatorname {diag}(t^{\tau _A(i) - \tau _A(i_0)})\). Tightness makes \(T\) invariant under \(\lambda (t) \otimes \mu (t) \otimes \nu (t)\) for suitable diagonal \(\mu , \nu \), so conjugating and using that only the kernel matters gives the same bound for the projection along \(\lambda (t) u\), for every \(t \ne 0\). As \(t \to 0\), \(\lambda (t) u \to u_{i_0} a_{i_0}\), because \(\tau _A(i) {\gt} \tau _A(i_0)\) for every other \(i\) in the support (\(\tau _A\) is injective). The directions \(v \ne 0\) satisfying the bound form a closed subset of \(A \setminus \{ 0\} \), and \(\Pi _{a_{i_0}}\) has the same kernel as the map that zeroes slice \(i_0\). This one-parameter-subgroup limit replaces the Borel fixed-point theorem used by Landsberg and Michałek.

Apply Lemma 1391 and then Lemma 1392 to the tight tensor \(T|_S\). If the zeroed slice lies outside \(S\), the bound already holds for \(T|_S\) and deleting any element of \(S\) keeps it. Iterating gives the ordering. Once the bound reaches \(0\), \(T|_{S_q} = 0\), which is impossible while \(S_q\) contains a nonzero slice; hence \(|S_0| \le r\).

Since \((n - r) + (n - s) + (r + s) = 2n\), \(\Phi _n \ge 2n/3\). The bound \(\Phi _n(r, s) \le T\) forces \(r \ge n - T\), \(r + s \le T\), and either \(2(r + s) \le T\) or \(2(n - r - s) \le T\), which gives the two intervals. If the first is empty, the second has at most \(3T/2 - n + 1\) points. Otherwise \(s \le 3T/2 - n\), and the second interval, capped at \(k\), has at most \(T/2 + s - k\) points, for a total of at most \(2T - n - k + 1 \le 3T/2 - n + 3/2\) when \(T \le n\). When \(T \ge n\) the bound is at least \(k\).

Let \(S_q\) be the survivors after \(q\) deletions. Before any deletion the first block of each sign has \(L \ge R\) slices, so both signs have a good block; after all \(m\) deletions neither has. At the last stage \(q\) at which both signs have a good block, the next deletion removes one slice and leaves one sign without a good block. Say it is the negative sign; otherwise exchange the signs, using \(\Phi _m(r, s) = \Phi _m(s, r)\). Then \(S_q\) has at most \((R - 1)(k/L + 1) + 1\) negative slices. Fix a good negative block \(B^-\) for \(S_q\) and write \(\mathrm{LB}(S_q) = D(T - E)\). Each good positive block \(B\) pairs with \(B^-\) to give offsets \(r_B \in B\) and \(-s_B \in B^-\) with \(\Phi _m(r_B, s_B) \le T\), so in particular \(T \ge 2m/3\). All \(s_B\) lie within \(L\) of one \(s_0\), and every surviving offset \(r\) of \(B\) lies within \(L\) of \(r_B\), so \(\Phi _m(r, s_0) \le T + 4L\). By the two-interval lemma at most \((3(T + 4L) - 2m + 3)/2\) slices survive in good positive blocks. The other positive blocks hold at most \(R - 1\) survivors each, and offset \(0\) at most one. Hence \(q = m - |S_q| \ge 2m - 3T/2 - O(L + Rm/L)\) and \(q + \mathrm{LB}(S_q) \ge 2m + (D - 3/2)T - DE - O(L + Rm/L)\), which is at least the stated bound because \(D \ge 3/2\) and \(T \ge 2m/3\). For the tensor, border substitution (Theorem 1393) gives an ordering with \(q + \underline{\mathbf{R}}(T|_{S_q}) \le \underline{\mathbf{R}}(T)\) for every \(q \le m\).

Choose \(x_0, x_1, \dots \) greedily, keeping the invariant that no combination \(\sum _t \varepsilon _t x_t\) with \(\varepsilon _t \in \{ -1, 0, 1\} \), not all zero, vanishes; this is equivalent to distinct subset sums. After \(i \le n\) choices the signed sums \(\sum _t \varepsilon _t x_t\) take at most \(3^i {\lt} |A|\) values, so some \(a \in A\) avoids them. A vanishing combination of \(x_0, \dots , x_{i-1}, a\) has coefficient \(0\) on \(a\), and then vanishes by the invariant, or coefficient \(\pm 1\), which would make \(a\) a signed sum. Sorting the chosen set keeps its subset sums distinct. For a cluster, apply this to the offsets of the slices of \(S\) in the block, which are at most \(L\) consecutive integers of one sign. A greedy choice that only keeps the \(p\)-subset sums distinct can get stuck.

Its support lies on \(\ell = j + (a - k)\). Slice \(a\) has the entry \(\gamma _{a, j}\) at \(j = k - a\), \(\ell = 0\) when \(a \le k\), and at \(j = 0\), \(\ell = a - k\) otherwise.

Corollary 1389 is \(\mathrm{PK}(k, p, L, 8(p + 1)L)\). Let a positive and a negative block each keep at least \(R = 3^{2p} + 1\) slices of \(S\). Lemma 1397 gives a cluster in each, and their median slices witness the paired-cluster hypothesis of Definition 1394 for \(S \mapsto \underline{\mathbf{R}}(T_k|_S)\), with \(D = (2p + 1)/(p + 1)\) and \(E = 8(p + 1)L\). The tensor is tight with nonzero slices (Lemma 1398), and \(D \ge 3/2\) since \(p \ge 1\), so Theorem 1396 gives \(\underline{\mathbf{R}}(T_k) \ge (1 + 2D/3)m - DE - (8L + Rm/L + 2)\), where \(1 + 2D/3 = 7/3 - 2/(3(p + 1))\) and \(DE = 8(2p + 1)L\). For the asymptotic bound fix \(L \ge \max (R, 2R/\delta )\): then \(Rm/L \le \delta m/2\), and the constant \(16(p + 1)L + 2\) is at most \(\delta m/2\) for large \(k\). For \(7/3 - \varepsilon \) choose \(p\) with \(2/(3(p + 1)) {\lt} \varepsilon \) and \(\delta = \varepsilon - 2/(3(p + 1))\).

Since \((a \bmod A) M + (j \bmod M) {\lt} AM\), every coefficient is \(2^{2^e}\) with \(e {\lt} AM\). Equal codes give \(a \equiv a' \pmod A\) and \(j \equiv j' \pmod M\), so they separate the positions with \(|a - a'| \le L {\lt} A\) and \(|j - j'| \le pL {\lt} M\). The certificates compare labels only within such a window (Theorem 1388 and Lemma 1385), so Corollary 1389 gives \(\mathrm{PK}_{P_k}(p, L, 8(p + 1)L)\). The tensor \(P_k\) is tight with nonzero slices (Lemma 1398), and the argument of Theorem 1400 applies verbatim. For the asymptotic bounds fix \(p\), then \(L \ge \max (3^{2p} + 1, 2(3^{2p} + 1)/\delta )\), then \(A = L + 1\) and \(M = pL + 1\); for \((21/10)m\) take \(p = 2\) and \(\delta = 1/90\), so \(19/9 - \delta = 21/10\).

Every fixed positive \(p\) eventually passes all three guards, so the selected order tends to infinity. The periodic finite bound and the last guard give \((7/3-8/(3(p+1)))d\) for the core rank. Restriction to the core bounds the padded tensor’s border rank from below; \(d\ge m-1\) absorbs the padding loss. The period-product guard bounds the exponent code by \(\log _2d\), so an entry \(2^{2^e}\) has at most \(m+1\) bits. Sum over the \(m^3\) coordinates.

Split the variables into two halves and enumerate partial assignments. Map each to a vector over the clauses, after sparsification. First step: running times are measured in a parameter (the number of variables \(n\)) rather than input length, so fine-grained reductions need explicit time bounds in named parameters, beyond the existing \(\mathsf{DTIME}\).

With Hadamard and Toffoli gates all amplitudes are real: each amplitude is a signed count of computation paths divided by \(2^{h/2}\), where \(h\) is the number of Hadamard gates. Squaring, the acceptance probability is \((\# \text{positive} - \# \text{negative})/2^h\) over pairs of polynomially checkable paths that end in the same accepting basis state, which a \(\mathsf{PP}\) machine can compare with a threshold. First step: define the path-sum semantics of such circuits and prove it agrees with the matrix semantics on small examples.