Dependencies

If \(f\) has degree at most \(k\), then \(\lVert f \rVert _4 \le \sqrt{3}^{\, k}\, \lVert f \rVert _2\).

If \(X\) is nonempty, \(k{\gt}0\), and \(D_\infty (X)\le k\), then for every fixed \(S\), with probability at least \(63/64\) over \(x\sim X\), \(D_\infty (X_{x,S})\le 64k\).

The map \(f\mapsto \breve f\) is pointwise concave on nonnegative functions. If \(R\subseteq S\), then \(\breve f(S)\le \breve f(R)\). Furthermore, \(0\le \breve f(R)\le \mathbb {E}f=\breve f(\varnothing )\), and \(\breve f([n])\) is the harmonic mean of \(f\).

\(\lVert T_{1/\sqrt{3}} f \rVert _2 \le \lVert f \rVert _{4/3}\) for every \(f\).

For each fixed \(d\), every unbounded fan-in circuit of depth \(d\) computing the parity of \(n\) bits has size \(2^{\Omega (n^{1/d})}\). Håstad’s bound (Theorem 956) improves the exponent to \(n^{1/(d-1)}\).

If \(f\) is a degree-at-most-\(d\) polynomial threshold, \(0\le \rho \le 1\), and \(m\in \mathbb N\), then

Here \(\rho \) is the correlation parameter, so the corresponding bit-flip rate is \((1-\rho )/2\).

For every \(C{\gt}0\), some nonconstant finite Boolean function \(f\) requires exact decision-tree depth greater than \(C s(f)^2\). There are also a fixed \(\alpha {\gt}2\) and a family \(F_m\) such that every exact tree computing \(F_m\) has depth at least \(s(F_m)^\alpha \) for \(m\ge 1\). Every choice of exact trees for that family has depth tending to infinity.

There are oracles \(A\) and \(B\) with \(\mathsf{P}^A = \mathsf{NP}^A\) and \(\mathsf{P}^B \neq \mathsf{NP}^B\).

If for some \(\varepsilon {\gt} 0\) there is a pseudorandom function family in \(\mathsf{P/poly}\) against which no distinguisher of size \(2^{n^{\varepsilon }}\) has advantage \(2^{-n^{\varepsilon }}\) or more, then no \(\mathsf{P/poly}\)-constructive property of density at least \(2^{-O(n)}\) is useful against \(\mathsf{P/poly}\). The pseudorandomness hypothesis is an explicit assumption, not a proved fact.

\(\mathsf{BPP} \subseteq \mathsf{PAdvice}\).

For every \(\varepsilon {\gt}0\), eventually every exact scalar Fourier circuit has more than \((25/9-\varepsilon )n\) gates, in either representation. For every \(\varepsilon ,c{\gt}0\), arbitrarily large sizes admit CSLib circuits whose gate counts lie strictly between \((25/9-\varepsilon )n\) and \(cn\log _2n\). Consequently no positive eventual \(n\log _2n\) lower bound holds in this unrestricted scalar model.

Some language is not in \(\mathsf{P/poly}\).

For every \(A{\gt}0\), eventually every OR-AND-OR or AND-OR-AND circuit computing \(F_{n+1}\) has more than \(2^{A\sqrt{n+1}}\) gates. The same OR-AND-OR lower bound holds for the complement of \(F_{n+1}\).

The imported language has the same unrestricted OR-of-CNF gate lower bound and the same real-margin and integer threshold-weight bounds when formulas are complexitylib’s canonical CNFs. The gate bound counts all clauses and conjunction gates, not merely top fan-in.

Under the same eventual width bound, if integer coefficients \(z_j\) satisfy

then

An integer bias can again be included as the coefficient of the empty CNF.

Fix \(s\ge 0\), and write \(d=\lfloor n/5\rfloor \) and \(k=\lceil 3(s+1)\sqrt d\rceil \). Eventually, every finite collection of width-\(k\) CNFs \(H_j\) and real coefficients \(a_j\) satisfying

has

A bias is allowed by including the empty, identically true CNF as a feature.

The original hard language belongs to \(\mathsf P\), and its one-bit verdict belongs to \(\mathsf{FP}\). Its balanced padding belongs to \(\mathsf P\), accepts exactly half of every positive-length input cube, and eventually requires more than \(2^{A\sqrt n}\) gates for every \(A{\gt}0\) in both depth-three polarities.

\(\mathsf{PAdvice} = \mathsf{P/poly}\).

Every symmetric function has depth-three circuits of size \(2^{O(\sqrt n)}\). In particular, majority has circuits of depth at most \(d\) and size \(2^{O(n^{1/(d-1)})}\) at each fixed \(d\ge 2\), with input-only negations in both statements.

Suppose \(Q_2\) is existential-SO definable, \(\operatorname {queryLanguage}(Q_1)\) is NP-hard, and \(Q_1\le _{\mathsf{FO}}Q_2\) under the universe-preserving API. Then \(\operatorname {queryLanguage}(Q_2)\) is NP-complete for the existing machine definitions. The source hardness is an explicit hypothesis.

For clusters as in Theorem 1388 inside a set \(S\) of slices, with medians \(r\) and \(-s\),

where \(\Phi _n\) is the width of Definition 1394. There is no condition on \(k\), \(p\), \(L\), \(r\), or \(s\). The same bound holds for \(T_k(\gamma )\) with coefficients \(2^{2^{e}}\) whose labels separate an \((L, pL)\) window, as in Theorem 1388.

\(\mathsf{NP} \subseteq \mathsf{IP}\).

\(\mathsf{AC}^0 \subsetneq \mathsf{TC}^0\).

Under the preceding source, advice, and size hypotheses, set \(e=t+2a+\lceil \log _2(a+1)\rceil +10\). If

the actual complete program has retained-law error at most \(2^{-t}\). The finite program guard uses this chosen local error exponent.

Choose \(e,L,m\) from \(n,a,t,o\) as above. Let the original law have normalized left and right factors given \(Z\), with a nonnegative honest-left joint point-mass envelope \(\mu \) of total at most \(2^{-m}\). Suppose the honest right input is conditionally uniform on \(m\) bits. For any two fixed unequal advice words of length \(a\), the actual \(o\)-bit truncated program output has error at most \(2^{-t}\), retaining the original \((Z,B)\) and the actual truncated tampered output. No size guard, reserve inequality, field instance, primitive extractor, or intermediate security witness is supplied by the caller. The source hypotheses govern feasibility; the theorem does not assert the reserve fits every left-input width. The selected runtime is certified below; later asymptotic family composition remains separate.

Every De Morgan formula computing the parity of \(n \ge 1\) bits has at least \(n^2\) leaves, and for \(n = 2^k\) the minimum number of leaves is exactly \(n^2\). For \(1 \le k \le n\), every De Morgan formula computing the threshold function “at least \(k\) of the \(n\) inputs are \(1\)” has at least \(k (n + 1 - k)\) leaves; for strict majority (\(k = \lfloor n/2 \rfloor + 1\), ties rejected) this is \((n - \lfloor n/2 \rfloor )(\lfloor n/2 \rfloor + 1)\), which equals \(((n + 1)/2)^2\) for odd \(n\).

Under the hypotheses of Theorem 363, if \(20\, s(n) \le n\) for all large \(n\), then every single-output full-binary-basis circuit computing the length-\(n\) member whose shared gates have total fan-out at most \(s(n)\) satisfies \(n^2 \le 128(c+3)\log _2 n\, (\mathrm{size} + s(n) + 1)\). If \(s(n) = o(n)\), such circuits have superlinear size. Only the reuse of computed gate outputs is restricted: the size is unrestricted and input variables may be read any number of times. With \(s = 0\) this is the formula bound of Theorem 363; it does not apply to general circuits, whose shared fan-out is typically proportional to their size.

If moreover \(f\) has at least \(2^{n - 2}\) accepting inputs, then every split satisfies \(n \le \max (i + |B|, n - i + |A|) + \lceil \log _2 K \rceil + 2\), and hence \(\max (i + |B|, n - i + |A|) {\gt} n - \log _2 K - 3\). In particular, for every injective ranking of the wires some prefix, the wires ranked below a threshold, is crossed by at least \(\lfloor n/2 \rfloor - \lceil \log _2 K \rceil - 2\) forward and backward signals.

Let the inputs have in-degree zero and every vertex in-degree at most two. Under the hypotheses of Theorem 786, for every \(\varepsilon {\gt}0\) and all large \(N\) every such \(N\)-superconcentrator has at least \((1+1/A-\varepsilon )N\) vertices that are not inputs. This is \((4-\varepsilon )N\) for \(A=1/3\), the corresponding bound of Lev and Valiant, and \(\bigl(1+\pi /(3\arccos \tfrac {1+2\sqrt2}{4})-\varepsilon \bigr)N\approx (4.5625-\varepsilon )N\) for the edge-score coefficient.

For the polynomial-time family \(\mathrm{sourceReductionHardFamily}\) of Theorem 912, for every \(k\ge 1\) and \(\varepsilon {\gt}0\) and all large \(n\), every OR of CNFs of width at most \(k\) and every AND of DNFs of width at most \(k\) computing it has at least \(2^{(1/k-\varepsilon )n}\) CNFs, respectively DNFs.

For every \(\varepsilon {\gt}0\) and all sufficiently large \(p\), let \(F:\{ 0,1\} ^{2p}\to \{ 0,1\} ^m\) with \(m\le 2p\). If

then every circuit with at most \(s\) gates disagrees with \(F\) on more than \(2^p\) input rows. For a scalar function, replace \(3\) by \(1\). The thresholds are uniform in the functions and in \(s\).

Let \(F_p,G_p\) be vector functions on \(2p\) bits, with arbitrary common output width depending on \(p\). Suppose that eventually they differ on at most \(2^p\) rows and at most \(2p\) output coordinates. If \(2^p=o(C(F_p))\), then

\(\mathsf{TC}^0 \not\subseteq \mathsf{AC}^0[3]\).

Let \(f\) be two-sided \(K\)-rectangle-free with \(K\le 2^k\), and let a weighted threshold program with \(s_{\mathrm{in}}\) input-reading gates compute \(f\). Then:

1. (C1) \(2^n{\lt}4K^2\cdot 4^{s_{\mathrm{in}}}\), so \(n{\lt}2k+2+2s_{\mathrm{in}}\);

2. (C2) if every input weight vector is a real multiple of one vector, \(2^n{\lt}16K^2\cdot 2^{s_{\mathrm{in}}}\), so \(n{\lt}2k+4+s_{\mathrm{in}}\);

3. (C3) if the gates split into \(B\) direction runs, \(2^n{\lt}4K^2\cdot 4^B\cdot 2^{s_{\mathrm{in}}}\), so \(n{\lt}2k+2+2B+s_{\mathrm{in}}\).

Let \(f\) be two-sided \(K\)-rectangle-free with \(K\le 2^k\). (C2\('\)) If \(f(x)=F(\langle w,x\rangle )\) for a function \(F:\mathbb {R}\to \{ 0,1\} \) changing at most \(T\) times, then \(2^n{\lt}4K^2\max (1,4T)\), and \(T{\gt}2^{n-2k-4}\) when \(2k+4\le n\). (C4) If an activation program computes \(f\) and the activation of each input-reading gate \(j\) changes at most \(T_j\) times, then \(2^n{\lt}4K^2\prod _j\max (1,4T_j)\), the product ranging over the input-reading gates.

Let \(C\) be a circuit whose dependency graph has longest paths of at most \(2^k\) vertices, and let \(r \le k\). There is a set \(F\) of dependency edges with \(k\, |F| \le r \cdot \mathrm{totalFanIn}(C)\) whose removal leaves a graph whose longest paths have at most \(2^{k-r}\) vertices.

For the concrete universal machine \(\mathtt{utmTM}\): every string has finite plain complexity, and there are constants \(c, a, k\) with \(C^t_{\mathtt{utmTM}}(x) \le |x| + c\) whenever \(t \ge a(2|x|+3)^k\).

The binary NFA with \(9(n+2)\) states constructed above has a complement whose every \(s\)-state two-way nondeterministic recognizer satisfies

Consequently no real polynomial in the source state count bounds complementation of all ordinary binary NFAs by two-way NFAs. The statement concerns the complement of the full binary language.

For every \(n\), there is a binary Mathlib NFA with exactly \(9(n+2)\) states such that every \(s\)-state two-way deterministic recognizer of its language satisfies

Here \(\delta =2\) for positive-run acceptance and \(\delta =1\) otherwise. This is a statement about the full language accepted by the NFA.

For any alphabet and any code mapping relation letters on \(h\ge 2\) vertices to words, every \(s\)-state two-way NFA agreeing with the complement of liveness on all encoded words satisfies \(2^{\lfloor (h-2)/127\rfloor }\le 2(s+1)\). The code lengths and behavior outside the encoded words are unrestricted.

Let \(c\) map relation letters on \(h\ge 2\) points to words over any alphabet. Extend \(c\) to words by concatenation. If an \(s\)-state two-way deterministic automaton accepts \(c(w)\) exactly when \(w\) is live, then

with the same acceptance-convention constant \(\delta \) as above. There is no code-length assumption or loss in the state bound. The automaton’s answers on other words are unrestricted by the hypothesis.

Under either acceptance convention, there are no constants \(C,c{\gt}0\) such that every \(n\)-state one-way nondeterministic automaton over every finite alphabet has an equivalent two-way deterministic automaton with at most \(Cn^c\) states. Consequently, such a simulation is impossible for unrestricted two-way nondeterministic automata as well.

The complement of \(\mathrm{SAT}\) (as a set of bit strings, so including all malformed strings) is \(\mathsf{coNP}\)-complete. \(\mathrm{SAT} \in \mathsf{P} \iff \mathsf{P} = \mathsf{NP}\), and \(\mathrm{SAT} \in \mathsf{coNP} \iff \mathsf{NP} = \mathsf{coNP}\).

Let \(C\) be a fan-in-two circuit with \(s + a\) inputs, \(a \ge 1\), and \(M \ge 1\) outputs, whose first \(s\) inputs are a random seed, and let a decidable predicate say which outputs are correct for which inputs \(u \in \{ 0,1\} ^a\). If for every \(u\) the seeds \(\sigma \) on which \(C(\sigma u)\) is incorrect for \(u\) have probability at most \(2^{-(a+1)}\), then one seed is correct for every \(u\), and hardwiring it gives a circuit on \(a\) inputs with the same internal gate count and the same size that is correct for every \(u\).

Now fix \(q \ge 1\), \(t\), and sets \(S_u \subseteq \{ 0,1\} ^n\) for \(u \in \{ 0,1\} ^a\), and say \(C\) implements the relative estimator if, for every seed \(\sigma \) and every \(u\), the output of \(C(\sigma u)\) read as a little-endian unsigned integer equals the output of the estimator of Theorem 216 on \(S_u\) with seed \(\sigma \). Then \(C\) fails to output a relative-error-\(1/q\) approximation of \(|S_u|\) exactly on the estimator’s failure seeds, hence with probability at most \(2^{-t}\) for every \(u\); for \(t = a + 1\), hardwiring a seed gives a circuit of the same size that is accurate on every \(u\). The same holds for a fixed-round adaptive oracle program of fan-in-two circuits (AdaptiveOracleProgram): inlining circuits that answer every query of the right width as the oracle does preserves implementing the estimator, and if the program implements it with \(t = a + 1\) relative to every oracle deciding a language \(A \in \mathsf{P/poly}\), then for some polynomial-size circuit family deciding \(A\), inlining that family and hardwiring a seed gives an ordinary circuit, of the same size as the inlined program, that is accurate on every \(u\).

\(\mathsf{BPP} \subseteq \mathsf{PH}\).

\(\mathsf{BPP} \subseteq \mathsf{PSPACE}\).

Every \(F : \{ 0,1\} ^n \to \{ 0,1\} \) on bit strings determines the Boolean-valued function \(x \mapsto \chi (F(x))\) on the cube. This must be a public bridge. The PCP development has only a related map, Complexity.signOf in an internal module, which sends an \(\mathbb {F}_2\)-valued function on the cube to its \(\pm 1\) encoding. It does not act on bit strings.

The convolution is \((f * g)(x) = \mathbb {E}_y[f(y)\, g(x + y)]\). A density is a nonnegative \(\varphi \) with \(\mathbb {E}[\varphi ] = 1\). The density of a nonempty set \(A\) is \(\varphi _A = 1_A / \mathbb {E}[1_A]\). For \(A = \emptyset \) the Lean definition divides by zero and returns the zero function, so theorems about \(\varphi _A\) assume \(A\) is nonempty.

For nonempty \(X\subseteq \{ 0,1\} ^I\), let \(\mu _X\) be its uniform mass function and \(D_\infty (X)=|I|-\log _2|X|\). Given \(S\subseteq I\) and \(x\in X\), the fiber \(X_{x,S}\) consists of patterns on \(S\) whose completion using \(x\) outside \(S\) belongs to \(X\). Its deficit is measured relative to the \(|S|\)-dimensional cube. The real-valued Lean definition takes value \(|I|\) at the empty set; entropy interpretations require nonemptiness. Write \(x[S\leftarrow y]\) for replacing \(x\) on \(S\) using \(y\), \(\rho _X(S,x)=|X_{x,S}|/2^{|S|}\) for the fiber density, and \(f_X=2^{|I|}\mu _X\) for the normalized cube density.

For a real mass function \(\mu \) on the cube, define \(\mu _R(z)=\sum _{x:x_R=z}\mu (x)\). If \(\mu \ge 0\) and \(\sum _x\mu (x)=1\), this is the probability of the pattern \(z\) under the marginal distribution.

\(\mathrm{BooleanFunction}(n)\) is the real vector space of functions \(f : \mathbb {F}_2^n \to \mathbb {R}\). Its inner product space structure comes from the uniform-measure inner product \(\langle f, g \rangle = 2^{-n} \sum _x f(x) g(x)\). The uniform expectation \(\mathbb {E}[f]\) is the average of \(f\) over the cube, so \(\mathbb {E}[f] = 2^{-n} \sum _x f(x)\) and \(\langle f, g \rangle = \mathbb {E}_x[f(x) g(x)]\). The type is a def rather than an abbrev, so the \(L^2\) norm does not clash with Mathlib’s sup norm on function types.

The degree-\(k\) part of \(f\) is \(f^{=k} = \sum _{|S| = k} \widehat{f}(S) \chi _S\), and \(f^{\le k} = \sum _{|S| \le k} \widehat{f}(S) \chi _S\). The weight above degree \(k\) is \(W^{{\gt}k}[f] = \sum _{|S| {\gt} k} \widehat{f}(S)^2\). The degree of \(f\) is \(\max \{ |S| : \widehat{f}(S) \neq 0\} \), valued in \(\mathbb {N} \cup \{ \bot \} \) with \(\bot \) for \(f = 0\). For Boolean-valued \(f\), the spectral sample is the probability distribution \(S \mapsto \widehat{f}(S)^2\) on subsets of \([n]\).

A point \(x\) is a \((p,k)\)-limit of \(Y\) if \(\Pr _{P\subseteq _p I}[\rho _Y(P,x)\ge 2^{-k}]\ge 3/4\).

\(x^{\oplus i}\) flips coordinate \(i\) of \(x\). This is an involutive equivalence of the cube. The derivative is defined spectrally: \(D_i f = \sum _{S \ni i} \widehat{f}(S)\, \chi _{S \setminus \{ i\} }\). The sensitivity operator is \(L_i f(x) = (f(x) - f(x^{\oplus i}))/2\). These are different operators: by Theorem 1195, \(D_i\) removes \(i\) from each frequency, while \(L_i\) keeps only the frequencies that contain \(i\).

The Fourier coefficient of \(f\) on \(S\) is \(\widehat{f}(S) = \langle f, \chi _S \rangle \), and its Fourier weight is \(\widehat{f}(S)^2\). The weight at degree \(k\) is \(W^k[f] = \sum _{|S| = k} \widehat{f}(S)^2\).

For nonnegative \(f\) on a nonempty finite set, its harmonic mean is \((\mathbb {E}_x f(x)^{-1})^{-1}\) if all entries are positive, and zero otherwise. On the Boolean cube, let \(f_R(z)=\mathbb {E}[f(x)\mid x_R=z]\). The harmonic transform is \(\breve f(R)=(\mathbb {E}_z f_R(z)^{-1})^{-1}\), with the same zero convention. Bernoulli coordinate expectations assign a mask \(R\) weight \(p^{|R|}(1-p)^{n-|R|}\).

Spectrally, \(\mathrm{Inf}_i[f] = \sum _{S \ni i} \widehat{f}(S)^2\) and \(\mathbf{I}[f] = \sum _S |S|\, \widehat{f}(S)^2\).

\(f\) is linear if \(f = \chi _S\) for some \(S\). It is multiplicative if \(f(x + y) = f(x) f(y)\) for all \(x, y\). It is \(\varepsilon \)-close to \(g\) if \(\mathrm{dist}(f, g) \le \varepsilon \), and \(\varepsilon \)-close to a property \(P\) if it is \(\varepsilon \)-close to some \(g\) satisfying \(P\). The BLR acceptance probability is \(\Pr _{x,y}[f(x) f(y) = f(x + y)]\) for independent uniform \(x\) and \(y\).

For real \(p \ge 1\), \(\lVert f \rVert _p = \mathbb {E}[|f|^p]^{1/p}\) under the uniform measure. It should agree with the existing \(L^2\) norm at \(p = 2\) and satisfy Hölder’s inequality.

\(\mathrm{Var}[f] = \mathbb {E}[f^2] - \mathbb {E}[f]^2\) and \(\mathrm{Cov}[f,g] = \mathbb {E}[fg] - \mathbb {E}[f]\mathbb {E}[g]\). The uniform probability of a predicate \(P\) is \(\Pr [P] = \mathbb {E}[1_P]\), where \(1_P\) is the \(0\)–\(1\) indicator of \(P\), and the relative Hamming distance is \(\mathrm{dist}(f,g) = \Pr _x[f(x) \neq g(x)]\).

Order the cube coordinatewise by the values \(\chi (x_i) \in \{ -1, 1\} \). So \(x \le y\) iff \(y\) is obtained from \(x\) by changing some coordinates from \(1\) to \(0\). A function \(f\) is monotone if \(x \le y\) implies \(f(x) \le f(y)\). This is O’Donnell’s order on \(\{ -1,1\} ^n\). It is the reverse of the bitwise order on \(\mathbb {F}_2^n\), and the Lean definition must record the choice explicitly. The circuit library’s IsMonotoneBoolFun is a different notion: monotonicity of \(\{ 0,1\} \)-valued functions on bit strings in the bitwise order.

All four are defined spectrally, for \(\rho \in \mathbb {R}\):

• \(\mathrm{Stab}_\rho [f] = \sum _S \rho ^{|S|} \widehat{f}(S)^2\);

• \(\mathrm{Stab}_\rho [f,g] = \sum _S \rho ^{|S|} \widehat{f}(S)\widehat{g}(S)\);

• the noise (Bonami–Beckner) operator \(T_\rho f = \sum _S \rho ^{|S|} \widehat{f}(S) \chi _S\);

• \(\mathrm{NS}_\rho [f] = (\langle f, f \rangle - \mathrm{Stab}_\rho [f])/2\).

\(\chi : \mathbb {F}_2 \to \mathbb {R}\) sends \(b \mapsto (-1)^b\). For \(S \subseteq [n]\), the parity function is \(\chi _S(x) = \prod _{i \in S} \chi (x_i)\), so \(\chi _\emptyset = 1\). A function is Boolean-valued if every value is \(1\) or \(-1\).

Set \(\ell =2m+1\). Inputs have \(k\) blocks of \(\ell \) bits, represented either by their true-coordinate subsets or by ordinary \(\mathbb F_2\) assignments. Write \(h_i(x)=[|x^{(i)}|{\gt}m]\) and \(H(x)=\sum _i h_i(x)\) in \(\mathbb F_2\). Define \(\operatorname {corr}(f,g)=|\mathbb E_x(-1)^{f(x)+g(x)}|\) for uniform \(x\), and \(N_{m,d}=\# \{ A\subseteq [\ell ]:|A|\le m{\lt}|A|+d\} \).

For \(p\in \mathbb R[X_1,\ldots ,X_n]\), let \(f_p(x)=\operatorname {sign}(p(\chi (x_1),\ldots ,\chi (x_n)))\), with \(\operatorname {sign}(0)=1\). A function is a degree-at-most-\(d\) polynomial threshold if it is \(f_p\) for some \(p\) of total degree at most \(d\). Its sign-cube multilinearization reduces each monomial exponent modulo two.

Let \(V_m\) span the squarefree monomials \(x^A\) with \(|A|\le m\). A product generator \(x^{\mathbf A}h^S\) has weight \((m+1)|S|+\sum _{i\notin S}|A_i|\), with each \(|A_i|\le m\). Let \(F_r\) be the span of generators of weight at most \(r\).

For a finite Boolean function \(f\), let \(s(f,x)\) count coordinates whose individual flips change \(f(x)\). Let \(\operatorname {bs}(f,x)\) be the maximum number of pairwise disjoint nonempty coordinate blocks whose flips change \(f(x)\). Write \(s(f)\) and \(\operatorname {bs}(f)\) for the maxima over inputs.

Hirahara’s 2018 distribution \(D^u\): at parameter \(m {\gt} 0\), choose \(n \in \{ 0, \dots , m-1\} \) uniformly and \(x \in \{ 0,1\} ^n\) uniformly, and output \(\mathrm{pair}(x, 1^{m-n})\). The library realizes this with the seed space \(\{ 0, \dots , m-1\} \times \{ 0,1\} ^m\), keeping the first \(n\) bits of the \(m\)-bit string as \(x\), so the slice has \(m \cdot 2^m\) equiprobable seeds. The parameter \(m\) is the sum \(|x| + (m-n)\) of the component lengths, not the length of the encoded pair. The slice \(m = 0\) is totalized as the point \(\mathrm{pair}(\epsilon , \epsilon )\) (a single seed), a library convention.

A heuristic is a deterministic map from strings to the three answers accept, reject and fail; it is errorless for \(L\) if it never accepts outside \(L\) and never rejects inside \(L\). It runs in polynomial time when its answer, encoded as \([\mathrm{true}]\), \([\mathrm{false}]\) or the empty string respectively, is a function in \(\mathsf{FP}\). A distributional problem is a language with a finite ensemble of input strings. For \(\delta \colon \mathbb {N} \to \mathbb {Q}\), \(\mathsf{AvgP}_\delta \) consists of the distributional problems having a polynomial-time errorless heuristic whose failure probability on slice \(n\) is at most \(\delta (n)\) for every \(n\). \(\mathsf{AvgP} = \bigcap _{c \in \mathbb {N}} \mathsf{AvgP}_{\delta _c}\) with \(\delta _c(n) = 1/\max (1,n)^c\), which is \(n^{-c}\) for \(n \ge 1\) and \(1\) at \(n = 0\): for each \(c\) there is a possibly different polynomial-time errorless heuristic meeting \(\delta _c\). This is not the single-scheme formulation in which the heuristic receives \(1/\delta \) as an input; relating the two is part of Definition 1135. The heuristic does not receive \(n\), and its time is polynomial in the sample length \(|x|\); since samples need not have length \(n\), this is stricter than the textbook bound polynomial in \(n\) when samples are much shorter than \(n\), so Definition 1134 should require samples of length polynomially related to \(n\).

A generator is any map \(G \colon \{ 0,1\} ^d \to \{ 0,1\} ^m\) (no efficiency is built in). A test \(T \subseteq \{ 0,1\} ^m\) has distinguishing advantage \(|\Pr _s[G(s) \in T] - \Pr _y[y \in T]|\). Relative to a machine \(M\), clock \(t\) and threshold \(r\): \(T\) is a random test if every \(y \in T\) has \(C^t_M(y) \ge r\); \(T\) is \(\delta \)-dense if \(\Pr _y[y \in T] \ge \delta \); and \(G\) has low complexity if every output satisfies \(C^t_M(G(s)) {\lt} r\).

For an oracle machine \(N\) and Boolean oracle \(A\), \(C^{t,A}_N(x)\) is the minimum length of a program on which \(N^A\) produces \(x\) within \(t\) steps (\(\infty \) if there is none). The random-access oracle of a string \(y\) answers canonical tagged queries “bit \(i\) of \(y\)” and “is \(i {\lt} |y|\)” (malformed and out-of-range queries answer false), so it determines both the contents and the length of \(y\). Conditional complexity is \(C^t_N(x \mid y) = C^{t, \mathrm{oracle}(y)}_N(x)\). Other conditioning conventions (sequential input, paper-specific evaluators) are not identified with this one.

\(\mathrm{cd}^{s,t}_M(x) = C^s_M(x) - C^t_M(x)\) and \(\mathrm{cd}^{s}_M(x) = C^s_M(x) - C_M(x)\), where the difference is \(\infty \) if either term is \(\infty \) and truncated natural subtraction otherwise. Both are defined for all clocks; the second subtraction is always exact, and the first is exact when \(s \le t\) (then \(C^t_M(x) \le C^s_M(x)\)), the case in which its laws are stated.

An ensemble is polynomial-time samplable when a single machine computes its sample map from a polynomially long seed in time polynomial in \(n\), with closure under polynomial-time maps, pairing, padding, products and efficiently chosen mixtures. \(\mathsf{DistNP}\) consists of pairs \((L, D)\) with \(L \in \mathsf{NP}\) and \(D\) polynomial-time samplable. Levin-style domination is kept as a separate notion if needed.

A finite ensemble assigns to each parameter \(n\) a nonempty finite seed space \(S_n\) (with decidable equality) and a sample map \(S_n \to \alpha \); the distribution at \(n\) is the pushforward of the uniform distribution on \(S_n\), with multiplicity. A dyadic ensemble is the special case \(S_n = \{ 0,1\} ^{\ell (n)}\), and its embedding into finite ensembles preserves every event probability. No sample map is called efficient until a machine realizes it (Definition 1134). Samples need not have length \(n\).

Hirahara 2022, Definitions 6.1 and 6.5. Fix an ordinary machine \(M\) and a conditional oracle machine \(N\). For a widening trivariate clock \(\tau (|x|, |y|, t) \ge t\), the promise \(\mathsf{GapMINcKT}\) on canonical \((x, y, 1^t, 1^s)\) has yes side \(C^t_N(x \mid y) + \mathrm{cd}^{t,\tau }_M(y) \le s\) and no side \(C^{\tau }_N(x \mid y) {\gt} s + \lfloor \log _2 \tau \rfloor \). The multiplicative version with factor \(\phi \colon \mathbb {N} \to \mathbb {N}\), \(\phi \ge 1\), has the same yes side and no side \(C^{\tau }_N(x \mid y) {\gt} \phi (|x|) \cdot s + \lfloor \log _2 \tau \rfloor \). A conditional estimator \(B\) satisfies Proposition 6.2’s sandwich if \(B(x, y, 1^t) \le C^t_N(x \mid y) + \mathrm{cd}^{t,\tau }_M(y)\) and \(C^{\tau }_N(x \mid y) \le B(x, y, 1^t) + \lfloor \log _2 \tau \rfloor \) on every instance.

Hirahara 2022, Definition 3.3: for a widening clock \(\tau (n, t) \ge t\), the promise on canonical \((x, 1^t, 1^s)\) with yes side \(C^t_U(x) \le s\) and no side \(C^{\tau }_U(x) {\gt} s + \lfloor \log _2 \tau \rfloor \), where \(\tau = \tau (|x|, t)\). An estimator \(B\) satisfies Fact 3.4’s sandwich if \(B(x, 1^t) \le C^t_U(x)\) and \(C^{\tau }_U(x) \le B(x, 1^t) + \lfloor \log _2 \tau \rfloor \) on every instance \((x, 1^t)\); it satisfies it on a set \(E\) of instances if these hold for every instance in \(E\).

Heuristics that may answer incorrectly on a set of bounded probability, \(\mathsf{Heur}_\delta \mathsf{P}\) and \(\mathsf{HeurP}\), the single-scheme versions of \(\mathsf{AvgP}\) and \(\mathsf{HeurP}\), randomized variants, and the standard amplification and inclusion lemmas.

An NW design is an ordered family \(S_1, \dots , S_m\) of \(\ell \)-element subsets of \([d]\), each enumerated injectively. It has overlap budget \(b\) if for every \(i\), \(\sum _{j{\lt}i} 2^{|S_i \cap S_j|} + (m - i) \le b\) (Hirahara’s weak-design cost). For \(f \colon \{ 0,1\} ^\ell \to \{ 0,1\} \) the generator is \(\mathrm{NW}^f(s) = (f(s|_{S_1}), \dots , f(s|_{S_m}))\).

Distributional Kolmogorov complexity, approximation-preserving padding, and the Meta-Complexity Padding Conjecture of Hirahara 2023 stated as an explicit hypothesis, together with its conditional characterization of one-way functions. It is never used as an unconditional theorem.

For an ordinary machine \(M\), a conditional oracle machine \(N\), a clock transformation \(\kappa \) and a loss \(\lambda \), \(\mathrm{SoI}(M, N, \kappa , \lambda )\) asserts, for all \(x, y, t\) with \(|x| + |y| \le t\),

The polynomial package asks for some \(\kappa \) with \(\kappa (t) \ge t\) and \(\kappa (t) \le a(t+1)^k\) for all \(t\), and \(\lambda (t) = \lfloor \log _2 \kappa (t) \rfloor + c\) for a constant \(c\). The inequality holds trivially wherever \(C^t_M(\mathrm{pair}(x,y)) = \infty \), in particular whenever \(t\) is too small for \(M\) to print \(\mathrm{pair}(x,y)\), and everywhere for a machine \(M\) that describes nothing; so SoI has content only for machines constrained by other hypotheses. (An earlier version also required \(C^t_M(\mathrm{pair}(x,y)) {\lt} \infty \) whenever \(|x| + |y| \le t\). That is impossible, since a run of \(t\) steps writes at most \(t\) output bits while \(|\mathrm{pair}(x,y)| = 2|x| + 2 + |y| {\gt} t\) at \(t = |x| + |y|\), and the requirement was removed.) SoI is a hypothesis; nothing in the library asserts it.

An enumeration \(i \mapsto (M_i, p_i)\) of oracle TMs paired with polynomial clocks such that every polynomial-time oracle language, relative to every oracle, is decided by some clocked \(M_i\), and the clocked machines are simulated uniformly in the oracle.

For a set \(P\) of Boolean functions on \(n\) bits (necessarily finite), its density is the exact rational \(|P| / 2^{2^n}\), the fraction of all Boolean functions on \(n\) bits that lie in \(P\).

A family of properties \(P_n\) of \(n\)-bit Boolean functions is large with density \(\delta (n)\) if \(\mathrm{density}(P_n) \ge \delta (n)\); constructive if membership of a truth table of length \(N = 2^n\) is decidable in time polynomial in \(N\) (or by circuits of size polynomial in \(N\)); and useful against \(\mathsf{SIZE}(s)\) if, for all sufficiently large \(n\), no function in \(P_n\) has circuits of size \(s(n)\). The quantifier over lengths and the scale of constructivity are part of the definition.

\(f : \mathbb {N} \to \mathbb {R}\) is negligible if for every \(c \in \mathbb {N}\) there is \(N {\gt} 0\) with \(|f(n)| {\lt} 1 / n^c\) for all \(n \ge N\).

Fix an oracle \(O\) and an oracle TM \(M\); all runs are relative to \(O\), and every step, local or lookup, counts toward a budget. \(M\) accepts \(x\) (within \(t\) steps) if the run on \(x\) reaches the halt state (after at most \(t\) steps) with output cell \(1\) equal to \(1\). \(M\) decides \(L\) in time \(T : \mathbb {N} \to \mathbb {N}\) if on every input \(x\) it reaches the halt state within \(T(|x|)\) steps, with output cell \(1\) equal to \(1\) if \(x \in L\) and equal to \(0\) if \(x \notin L\). \(M\) halts on a program \(p\) within \(t\) steps if the run on \(p\) reaches the halt state after at most \(t\) steps, and produces \(y\) on \(p\) within \(t\) steps if moreover the halted output tape has output \(y\). \(M\) halts on \(p\) (produces \(y\) on \(p\)) if it does so within some finite budget. These have the same shape as the corresponding definitions for ordinary machines.

An oracle NTM has two local transition functions selected by a choice bit and the same query mechanism and cost as an oracle TM, with execution along a fixed choice sequence and existential acceptance within a time bound.

A Boolean oracle is a function \(O : \{ 0,1\} ^* \to \{ 0,1\} \); it decides a language \(A\) if \(O(w) = 1 \iff w \in A\) for every \(w\). An oracle TM with \(k\) work tapes has a finite state type with decidable equality, a start state and a halt state; the input, \(k\) work and output tapes of an ordinary TM plus a dedicated read-write query tape; a partial map sending each query state to a pair (yes-successor, no-successor); and a local transition that reads the symbols under all heads (the query head included), writes symbols of \(\Gamma _w\) on the query, work and output tapes, and moves every head, moving right every head that reads \(\triangleright \). The initial configuration on \(x\) is in the start state with \(x\) on the input tape and every other tape empty. One step relative to \(O\) is defined as follows. The halt state has no successor. In a non-halted query state the machine reads the query word, formed by the cells strictly between the left marker and the query head in left-to-right order (a cell reads \(1\) only if it holds \(1\); \(0\), blank and \(\triangleright \) read as \(0\)), and enters the yes-successor if \(O\) answers \(1\) on it and the no-successor otherwise. The lookup costs exactly one step and changes nothing but the state; in particular the query tape is not erased, and writing the query costs ordinary local steps. Every other non-halted state applies the local transition. The relation \(c \to _O^t c'\) holds when \(c'\) is reached from \(c\) in exactly \(t\) steps relative to \(O\).

An oracle machine \(U\) simulates an oracle machine \(M\) under a compiler \(c : \{ 0,1\} ^* \to \{ 0,1\} ^*\) if for every oracle \(O\) and program \(p\): \(U\) halts on \(c(p)\) relative to \(O\) if and only if \(M\) halts on \(p\) relative to \(O\), and for every \(y\), \(U\) produces \(y\) on \(c(p)\) relative to \(O\) if and only if \(M\) produces \(y\) on \(p\) relative to \(O\). \(U\) simulates \(M\) under \(c\) in time \(\tau : \{ 0,1\} ^* \times \mathbb {N} \to \mathbb {N}\) if for every oracle \(O\), whenever \(M\) produces \(y\) on \(p\) within \(t\) steps relative to \(O\), \(U\) produces \(y\) on \(c(p)\) within \(\tau (p, t)\) steps relative to \(O\); unlike the ordinary timed simulation, bounded halting alone is not required to transfer. \(U\) is universal if for every \(k\) and every oracle machine \(M\) with \(k\) work tapes there is a compiler \(c\), computable by an ordinary deterministic machine, such that \(U\) simulates \(M\) under \(c\). For a policy of admissible clocks, \(U\) is efficiently universal for the policy if moreover \(c\) has additive overhead (\(|c(p)| \le |p| + C\)) and \(U\) simulates \(M\) under \(c\) in some admissible clock \(\tau \); it is efficiently universal if this holds for the polynomial policy, which admits \(\tau \) when \(\tau (p, t) \le a (|p| + t + 1)^e\) for some constants \(a, e\). In every case the compiler, constant and clock depend on \(M\) but are chosen once for all oracles.

A keyed family \(f_k : \{ 0,1\} ^n \to \{ 0,1\} \) computable in polynomial time, and its security game against a nonuniform class of distinguishers with oracle access (or with the full truth table): the advantage in telling \(f_k\) for a random key from a uniformly random function, required to be negligible, or bounded by an explicit function of the distinguisher’s size.

For a language \(A\), \(\mathsf{P}^A\) is the class of languages decided in polynomial time by an oracle TM relative to an oracle deciding \(A\), and \(\mathsf{NP}^A\) is the nondeterministic analogue. Query length is charged through the time needed to write the query.

Every TM with \(k\) work tapes is an oracle TM with \(k\) work tapes, the same states, start and halt state, and no query states. Its local transition applies the source transition to the input, work and output tapes and keeps the query tape inert: it writes only blanks there, and moves the query head right when it reads \(\triangleright \) and leaves it in place otherwise. Erasing the query tape maps an oracle configuration to the ordinary configuration with the same state and input, work and output tapes.

A bit string of length \(n\) is a function \(\{ 0, \dots , n-1\} \to \{ 0,1\} \). Circuits consume bit strings of a fixed length; machines consume lists.

\(\mathsf{BPTIME}(T)\) is the set of languages \(L\) for which there are a machine \(N\) (with any number of work tapes) and \(f = O(T)\) such that every path halts within \(f(|x|)\) steps, \(\mathrm{acceptProb}_N(x, f(|x|)) \ge 2/3\) for \(x \in L\), and \(\mathrm{acceptProb}_N(x, f(|x|)) \le 1/3\) for \(x \notin L\). \(\mathsf{BPP} = \bigcup _k \mathsf{BPTIME}(n^k)\).

A basis is a type of operations, each with an arity constraint (any fan-in, fan-in exactly \(k\), or fan-in at most \(k\)) and an evaluation map on bit strings of admissible length. A circuit over a basis \(B\) with \(N \ge 1\) inputs, \(M \ge 1\) outputs and \(G\) internal gates consists of \(G\) internal gates and \(M\) output gates. A gate applies an operation of \(B\) to a list of wires whose length the operation admits, and each gate input carries its own negation flag. The wires are the \(N\) inputs followed by the \(G\) internal gates. Internal gate \(i\) may read only wires \(0, \dots , N + i - 1\), so the circuit is acyclic by construction, and an output gate may read any wire. Evaluation \(C : \{ 0,1\} ^N \to \{ 0,1\} ^M\) gives each input wire its input bit and each gate the value of its operation on its input wires, each negated when its flag is set. The size of \(C\) is \(G + M\). The depth of an input wire is \(0\), the depth of a gate is one more than the largest depth of a wire it reads (\(1\) for a gate with no inputs), and the depth of \(C\) is the largest depth of an output gate.

For \(m \in \mathbb {N}\), the AND/OR/\(\mathrm{MOD}_m\) basis has AND, OR and \(\mathrm{MOD}_m\) gates of any fan-in, with the free negation flags on their inputs. A \(\mathrm{MOD}_m\) gate outputs \(1\) when the number of its inputs equal to \(1\) is not divisible by \(m\); since negations are free, the complementary convention defines the same classes. \(\mathsf{AC}^i[m]\) is defined like \(\mathsf{AC}^i\) over this basis, and \(\mathsf{AC}^0[m]\) is the case \(i = 0\).

The bases whose operations are AND and OR with fan-in exactly \(2\), with fan-in at most \(k\), and with any fan-in. In the last two a gate may have no inputs, and then computes the empty conjunction \(1\) or the empty disjunction \(0\). Negation is available only through the free per-input flags. Unless stated otherwise, a circuit is a circuit over the fan-in-two basis.

A width-\(w\) permutation branching program is a list of instructions \((i, \pi _0, \pi _1)\) with \(i \in \mathbb {N}\) and \(\pi _0, \pi _1 \in S_w\); the instruction reads variable \(i\). Under an assignment \(\alpha \), an instruction selects \(\pi _{\alpha (i)}\), and the program evaluates to the product \(\pi ^{(1)} \pi ^{(2)} \cdots \pi ^{(k)}\) of the selected permutations in \(S_w\), where \((\pi \tau )(y) = \pi (\tau (y))\). A program computes \(f\) through \(\sigma \) if, under every assignment \(\alpha \), it evaluates to \(\sigma \) when \(f(\alpha ) = 1\) and to the identity otherwise.

A fan-in-two single-output circuit is serialized as its gate count in terminated unary followed by its gates in index order, the output gate last. A gate is written as an operation bit, two negation flags, and two absolute wire references in terminated unary. The partial evaluator \(\mathrm{evalCode}(N, c, x)\) decodes \(c\), rejects inputs of the wrong length and codes that are malformed, have trailing bits, are empty, or reference a wire that is not yet computed, and evaluates the gates in order with a memo array. The code of a family at length \(0\) is the bit \(0\) followed by the stored answer; at length \(n \ge 1\) it is the bit \(1\) followed by the code of \(C_n\). The family evaluator runs a code \(c\) on a string \(x\) as follows: if \(x\) is empty, \(c\) must be \(0\, b\) for a bit \(b\), and the answer is \(b\); if \(x\) is nonempty, \(c\) must be \(1\, c'\), and the answer is \(\mathrm{evalCode}(|x|, c', x)\); every other case is rejected. The evaluation language is the set of strings \(\langle c, x \rangle \) (the library’s self-delimiting pairing) on which the family evaluator returns \(1\).

For selected gates \(S\), input \(x\), and guesses \(a:S\to U\), evaluate an unselected gate normally and a selected gate by its guess. The guess is consistent when each selected gate’s own operation, applied to the values of its argument wires under this evaluation, gives its guessed value.

A circuit is a straight-line program with addition, subtraction, and multiplication by a fixed complex scalar. Each operation costs one gate; inputs, a zero wire, fanout, and output selection are free. It computes \(F_n\) when its output equals \(F_nx\) for every complex input vector, where \((F_n)_{jk}=\exp (2\pi i/n)^{jk}\). Write \(L(n)\) for the least gate count of such a circuit.

The signature has zero, binary addition and subtraction, and unary scaling by each complex scalar. Translate the source’s free zero wire to an explicit zero gate, then copy each source gate and its wire references.

A circuit family over \(B\) consists of a single-output circuit \(C_n\) over \(B\) on \(n\) inputs, with any number of internal gates, for every \(n \ge 1\), together with an output bit for the empty input. It computes the Boolean function family given by \(C_n\) at length \(n \ge 1\) and by the stored bit at length \(0\), and it decides the language of strings on which it outputs \(1\). Its size at \(n \ge 1\) is the size of \(C_n\), and its size at \(0\) is \(0\). It has polynomial size if a single polynomial \(p \in \mathbb {N}[X]\) satisfies \(\mathrm{size}(n) \le p(n)\) for every \(n\).

A Boolean formula is a tree built from variables \(x_i\) (\(i \in \mathbb {N}\)), the two constants, negation, and binary conjunction and disjunction. It is evaluated under a total assignment \(\mathbb {N} \to \{ 0,1\} \). Its size is its number of nodes, its depth is the length of a longest root-to-leaf path, with each negation counted as one level, and its variables are the indices \(i\) of the variables \(x_i\) occurring in it.

\(\mathsf{FormulaNC1}\) is the class of Boolean function families computed by a family of formulas \((\varphi _n)\) in which \(\varphi _n\) reads only variables below \(n\), is evaluated on \(x \in \{ 0,1\} ^n\) under the assignment sending \(i {\lt} n\) to \(x_i\) (and every other index to \(0\)), and has depth at most \(c \lfloor \log _2 n \rfloor + c\) for a constant \(c\). \(\mathsf{Width5BP}\) is the class of Boolean function families decided by a family of width-\(5\) programs \(P_n\) for \(n \ge 1\), each reading only variables below \(n\) and with a designated point \(x_n\), together with an explicit answer at \(n = 0\); on \(x \in \{ 0,1\} ^n\) the output is \(1\) exactly when the value of \(P_n\) under the same assignment moves \(x_n\), and the length of \(P_n\) is at most \(C (n + 1)^k\) for constants \(C, k\).

Set \(F_{n+1}(b,x)=L(x)\mathbin \oplus b\). Interpret the same circuit wiring dually by exchanging AND and OR at every layer and complementing its literal and constant inputs. This gives an AND-OR-AND circuit with the same gate count.

Convert each canonical clause to its finite set of signed literals. For an OR of CNFs, place one bottom gate at every clause occurrence, one middle gate per CNF, and one top OR gate.

Replace each input variable by another variable or a Boolean constant, normalize each resulting clause, and discard tautological clauses. A CNF’s width is the maximum number of distinct variables in one clause.

Unfold the selected output wire over the unbounded AND/OR signature, pushing edge negations to leaves and removing repeated signed wire incidences first.

A depth-three circuit has bottom OR gates over signed literals and constants, middle AND gates over selected bottom gates, and one top OR gate. Lower gates can be shared. Fan-in is unrestricted at every layer. The gate count is the number of bottom and middle gates plus one.

A machine has finite control, a finite alphabet with a distinguished blank, and finitely many bilateral read-write tapes. One designated tape initially holds the input bits. A step reads all tape heads, then writes and moves them, or halts. A Boolean verdict is read from the halting control state. The time bound counts transitions to a halting configuration.

A Boolean function is symmetric when it is constant on each Hamming-weight level. Majority accepts precisely when \(2|x| \ge n\), including ties. A circuit has input-only negations when every negated gate argument reads a primary input; no internal gate output is negated.

A basis is complete if, for all \(N, M \ge 1\), every function \(\{ 0,1\} ^N \to \{ 0,1\} ^M\) is computed by some circuit over it; the fan-in-two AND/OR basis is complete. For \(N \ge 1\), \(f : \{ 0,1\} ^N \to \{ 0,1\} \) and a basis \(B\), \(\mathrm{size}_B(f)\) is the least size of a single-output circuit over \(B\) computing \(f\). The general version takes values in \(\mathbb {N} \cup \{ \infty \} \) and equals \(\infty \) exactly when no circuit over \(B\) computes \(f\). For a complete basis a natural-number-valued version is provided, and it agrees with the general one.

A threshold gate with cutoff \(t\) outputs \(1\) when at least \(t\) of its inputs are \(1\); the threshold basis has unweighted threshold gates of any fan-in, with the free negation flags on their inputs. \(\mathsf{TC}^i\) is defined like \(\mathsf{AC}^i\) over this basis.

A wire use is one gate-argument slot or one designated output; repeated occurrences count separately. Write \(u(v)\) for the number of uses of wire \(v\), \(w\) for the sum over original input wires, and \(e=\sum _{v\text{ a gate}}\max \{ u(v)-1,0\} \). A shared gate has \(u(v)\ge 2\). There are no unused gates when every gate has at least one use.

A function \(f : \{ 0,1\} ^* \to \{ 0,1\} ^*\) is computable if some deterministic machine, with any number of work tapes, computes \(f\).

\(\mathsf{coNL}\) is the class of languages whose complements are in \(\mathsf{NL}\).

\(\mathsf{coNP} = \{ L : \overline{L} \in \mathsf{NP}\} \), where \(\overline{L}\) is the complement of \(L\) in the set of all bit strings. The library forms every complement class with the same constructor (Complexity.complClass).

A tuple has the little-endian base-\(n\) index \(a_0+n a_1+\cdots +n^{k-1}a_{k-1}\). The address of a relation-table entry adds \(n+1\) for the header and the lengths of all earlier relation tables. A constant-table address adds the header, all relation-table lengths, \(cn\) for the preceding \(c\) constant blocks, and the chosen element’s value. Fixed-width tuple decoding repeatedly takes remainder and quotient by \(n\), recovering coordinates from an index in the same little-endian order.

Given a cardinality \(n\), a bit string, and natural-number variable values, evaluate terms and formulas directly by arithmetic table access. A constant is the first marked position in its one-hot block, or \(n\) if no position is marked. First-order quantifiers range over \(0,\ldots ,n-1\). The functions are total, including on malformed strings; semantic correctness requires a valid structure encoding and variable values in its universe.

A graph is bipartite if a Boolean color assignment gives different colors to the endpoints of every directed edge. Symmetry and loop-freeness are not assumed. Its proposed sentence is \(\exists X\, \forall x\, \forall y\, (E(x,y)\to (X(x)\leftrightarrow \neg X(y)))\).

Given a decidable graph and a Boolean color for each vertex, supply that color table to the two-universal-quantifier FO matrix of the bipartite sentence and evaluate the matrix.

At a fixed universe size \(n\), an input layout assigns wires to relation-table entries and one-hot constant blocks. There is a fixed finite numbering of all these sites, independent of the structure’s relation and constant values. Compile a formula under an assignment of its free variables as follows: relation atoms select a table entry by testing all argument values; equality tests whether both terms select the same value; negation uses De Morgan duality; Boolean connectives remain gates; and quantifiers become unbounded gates over the \(n\) possible values. The result is an AC0Formula.

Define \(P_\varphi \in \mathbb N[X]\) by \(P_{R(\bar t)}=1+(a+2)X^a\) for an \(a\)-ary relation, \(P_{t=u}=1+3X\), \(P_{\neg \varphi }=P_\varphi \), \(P_{\varphi \wedge \psi }=P_{\varphi \vee \psi }=1+P_\varphi +P_\psi \), and \(P_{Qx\, \varphi }=1+XP_\varphi \) for \(Q\in \{ \exists ,\forall \} \). This is the finite expansion used in Immerman, Section 5.4, Theorem 5.22.

A decision problem bundles a query with its isomorphism invariance. Logical definability supplies this law. Complement, intersection, and union inherit it. This is the interface of Senellart–Gnatenko, Section 3.1, restricted to our convention of at least two elements.

A computable parser \(\mathrm{dec} : \{ 0,1\} ^* \to V\text{-structures} \cup \{ \bot \} \). It checks the unary size and total length, reads relation bits and the first set bit in each constant block, and accepts only when re-encoding this candidate reproduces the entire input. It returns \(\bot \) on malformed input, including a size below \(2\), a constant block that is not one-hot, or trailing data.

A dimension-\(k\) interpretation defines the target universe as a definable subset of \(\mathrm{dom}^k\). Each target relation of arity \(a\) is defined by a formula with \(a k\) free variables. This requires a codec \(\mathrm{Fin}(n^k) \simeq (\mathrm{Fin}(k) \to \mathrm{Fin}(n))\) and a way to assemble environments for the \(a k\) variables.

For a fixed \(c{\gt}0\), interpret a graph on \(\mathrm{Fin}(c)\times \mathrm{Fin}(n)\) with \(E((i,x),(j,y))\) iff \(i=j\) and \(E(x,y)\) in the source. This defines the union of \(c\) disjoint copies and a reduction of bipartiteness to itself.

Give each source vertex a left and right copy. An output edge exists from \((0,x)\) to \((1,y)\) exactly when the source has \(E(x,y)\); no other tag pair carries an edge.

Evaluate the defining relation formulas to obtain a decidable target structure on the same universe, with constants copied from their designated source constants. The binary map decodes, interprets, and re-encodes, sending every malformed string to \([]\). A separate arithmetic generator writes the header, all target relation truth tables, and the designated one-hot constant blocks at a supplied cardinality, without validating the source string.

Decode the input string, evaluate the sentence on a successfully decoded structure, and return false if decoding fails.

A decidable structure of size \(n\) is encoded, computably, as the concatenation of three blocks:

• the size in unary, \(1^n 0\);

• for each relation symbol in index order, its truth table, listed over a computable enumeration of all tuples of its arity;

• for each constant symbol in index order, a one-hot block of length \(n\) whose bit \(i\) is \(1\) exactly when the constant is \(i\).

The encoding depends on the canonical order of \(\mathrm{Fin}(n)\).

Assign each relation and constant-table wire its actual bit position in the full structure encoding. Present an encoded structure as a Boolean input vector of length \(\ell _V(n)\). This layout is computable.

Enumerate relation and constant-table sites in the encoder’s order. A site’s bit position is its index in this list plus \(n+1\) for the unary prefix. The full length is \(\ell _V(n)=n+1+\sum _R n^{\mathrm{ar}(R)}+cn\).

At length \(\ell _V(n)\), conjoin the test \(n\ge 2\), a signed-literal test for the unary header \(1^n0\), and a one-hot test for every constant block. A one-hot test is a disjunction over the \(n\) possible values, each given by a conjunction of \(n\) signed literals. Relation-table bits are unrestricted. Write \(E_V(X)=X+4+c(1+X(1+X))\) for its size polynomial, with \(c\) constant symbols. The validated expansion conjoins this validator with the sentence expansion; its size polynomial is \(V_\varphi =1+E_V+P_\varphi \).

List the existential prefix’s arities from outermost to innermost. Consume one truth-table block at each relation quantifier, extending the Boolean relation environment. At the FO matrix, require an empty remaining certificate and run matrix evaluation. For an encoded input, first decode the structure and reject if decoding fails. These are computable functions.

To conjoin or disjoin two existential SO formulas, move each leading existential relation quantifier outward, weakening the other operand past its binder. Once both prefixes have been removed, conjoin or disjoin the matrices. The total operation is also defined on arbitrary SO formulas; it moves only their leading existential SO quantifiers. This implements the existential prefix manipulation in Immerman, Section 7.1.

A query is existential second-order definable if a sentence in \(\exists \mathsf{SO}\) prefix form defines it on every structure.

A formula is an FO matrix if it has no second-order quantifiers, though it may apply relation variables and use first-order quantifiers. It is in \(\exists \mathsf{SO}\) form if it is a possibly empty block of second-order existential quantifiers followed by an FO matrix.

A quantifier block binds the first \(k\) variables of a formula; its environment places the \(k\) coordinates before the old variables. Terms can be shifted across an entire block. Finite conjunctions and disjunctions are iterated binary connectives, with truth and falsity as their respective empty cases.

\(Q\) is first-order definable if some sentence \(\varphi \) satisfies \(Q(\mathcal{A}) \iff \mathcal{A} \models \varphi \) for every \(\mathcal{A}\).

For queries \(Q_1\) over \(V\) and \(Q_2\) over \(W\), \(Q_1 \le _{\mathsf{FO}} Q_2\) if some dimension-1 interpretation \(I : V \to W\) has \(Q_1(\mathcal{A}) \iff Q_2(I(\mathcal{A}))\) for all \(V\)-structures \(\mathcal{A}\). An interpretation is quantifier-free if every defining formula has quantifier rank \(0\). \(Q_1\) first-order projection reduces to \(Q_2\) if such an \(I\) can be chosen quantifier-free. This condition is coarser than Immerman’s projective form, in which each target bit depends on a single source bit.

An environment for \(k\) free variables is a map \(\mathrm{Fin}(k) \to \mathrm{Fin}(|\mathcal{A}|)\). Extending it by an element puts that element at index \(0\) and shifts the others. Satisfaction \(\mathcal{A}, \sigma \models \varphi \) is Tarskian, and quantifiers range over \(\mathrm{Fin}(|\mathcal{A}|)\). \(\mathcal{A} \models \varphi \) means satisfaction of a sentence under the empty environment.

Terms with \(k\) free variables are de Bruijn variables \(x_i\) (\(i {\lt} k\)) or constant symbols. Formulas are built from relation atoms, equality, \(\neg \), \(\wedge \), \(\vee \), \(\exists \), and \(\forall \). A quantifier binds variable \(0\) and shifts the others. Sentences are formulas with no free variables. Quantifier rank (the quantifier nesting depth) and size (the number of nodes) are defined by structural recursion.

For a formula with \(k\) free variables, scan the indices \(0,\ldots ,n^k-1\), decode each index into its \(k\) coordinates, and record the arithmetic evaluator’s verdict. This produces the relation table in the encoder’s order.

A dimension-1 interpretation \(I : V \to W\) consists of a \(V\)-formula with \(\mathrm{ar}(R)\) free variables for each relation symbol \(R\) of \(W\), and a source constant for each constant of \(W\). Applying \(I\) to a \(V\)-structure gives a \(W\)-structure on the same universe, in which \(R\) holds exactly where its defining formula does. Formulas translate backwards along \(I\), from \(W\) to \(V\): a target atom becomes its defining formula with the translated argument terms substituted, and a target constant becomes its source constant. Interpretations \(U \to V\) and \(V \to W\) compose to one \(U \to W\) by translating the outer defining formulas. The identity interpretation defines each relation by its own atom and sends each constant to itself.

An isomorphism \(\mathcal{A} \cong \mathcal{B}\) is a pair of mutually inverse maps between the universes whose forward map preserves and reflects every relation and preserves constants. Isomorphisms have identities, inverses, and composites. An embedding is an injective map that preserves and reflects every relation and preserves constants, as in model theory; its image is a substructure of \(\mathcal{B}\) isomorphic to \(\mathcal{A}\). Embeddings have identities and composites, and every isomorphism is one. An injective homomorphism only preserves relations, so \(\mathcal{B}\) may relate images of unrelated elements; every embedding is one. All three notions carry their maps as data.

\(\mathsf{FO}(\mathrm{LFP})\) extends first-order logic with \([\mathrm{lfp}_{R,\bar x}\, \varphi ](\bar t)\) for \(\varphi \) positive in \(R\). It is interpreted as the least fixed point of the monotone operator that \(\varphi \) induces on relations of the arity of \(R\). That fixed point is reached after at most \(n^{\mathrm{ar}(R)}\) iterations.

A Boolean relation environment assigns a Boolean table of the prescribed arity to every free relation variable. Interpret true bits as relation membership. Given an FO-matrix certificate, evaluate vocabulary atoms in the decidable structure, relation-variable atoms in these tables, and first-order quantifiers over the finite universe. Second-order quantifiers are excluded by the matrix certificate. Satisfaction with these inputs is decidable.

A computable \(\mathrm{Bool}\)-valued evaluator for first-order formulas on decidable structures. Atoms look up the \(\mathrm{Bool}\)-valued relations, and quantifiers become any and all over the list of universe elements. The sentence form runs it under the empty environment.

On \(\{ 0,\ldots ,n-1\} \), let \(\mathrm{BIT}(x,i)\) hold when bit \(i\) of \(x\) is one (counting from zero), \(\mathrm{ADD}(x,y,z)\) when \(x+y=z\) in \(\mathbb N\), and \(\mathrm{MUL}(x,y,z)\) when \(xy=z\) in \(\mathbb N\). The latter two are ternary relations restricted to the universe, without modular wraparound. Extend each input vocabulary by the selected predicates with these fixed semantics. Definability means agreement with a single sentence on every canonical expansion. The BIT profile adds only BIT; the arithmetic profile adds only ADD and MUL. These conventions follow Schweikardt and Schwentick, A note on the expressive power of linear orders, Section 2 (2011), https://lmcs.episciences.org/1008/pdf.

Append a designated binary relation for canonical strict order on \(\mathrm{Fin}(n)\), retaining the input relations and constants. Order atoms use the existing first-order syntax. Satisfaction on canonical expansions can depend on the labeling of the original structure. Derived successor and endpoint formulas remain planned.

A Boolean query over \(V\) is a property of finite \(V\)-structures. It is order-independent if isomorphic structures agree on it, that is, if it is invariant under isomorphism. Complement, intersection, and union are defined pointwise.

For each binary input length \(N\), define \(\mathrm{queryFamily}(Q)_N(x)=1\) exactly when the list of bits in \(x\) belongs to \(\mathrm{queryLanguage}(Q)\). This noncomputable characteristic family is defined for every query, including queries that are not decidable.

The language of \(Q\) is \(\{ \mathrm{enc}(\mathcal{A}) : \mathcal{A} \text{ decidable}, Q(\mathcal{A})\} \), where \(Q\) is applied to the structure that \(\mathcal{A}\) coerces to. By definition every string in it is an encoding, and the encoding of a decidable structure satisfying \(Q\) lies in it. This is the bridge from queries to the machine-model languages.

For a universe of size \(n\) and relation arities \(k_1,\ldots ,k_m\), concatenate the relation truth tables in context order, using the structure encoder’s tuple enumeration. The arities and \(n\) are external parameters, so no header is needed. The expected length is \(\sum _j n^{k_j}\). Direct reading supplies false for missing entries; the checked decoder accepts only the exact length.

\(Q\) is second-order definable if some second-order sentence \(\varphi \) satisfies \(Q(\mathcal{A}) \iff \mathcal{A} \models \varphi \) for every \(\mathcal{A}\).

Pull an SO formula back through a universe-preserving interpretation by replacing vocabulary atoms by their defining FO formulas. Translate constants and retain relation variables, relation arities and all quantifiers.

A relation renaming maps de Bruijn indices between contexts while preserving each relation’s arity. Its lift fixes a newly bound relation and renames the older variables. Weakening shifts all free relation indices past a fresh binder. Formula renaming lifts beneath both kinds of SO quantifier, leaving element variables and vocabulary symbols unchanged. Pullback reads a target relation environment at the renamed source indices.

A relation environment assigns to each relation variable in the context a \(\mathrm{Prop}\)-valued relation of its arity on the universe. Extending it puts the new relation at index \(0\). Satisfaction is defined under an element environment and a relation environment, and second-order quantifiers range over all \(\mathrm{Prop}\)-valued relations of the quantified arity on the universe. \(\mathcal{A} \models \varphi \) for a second-order sentence means satisfaction under the empty environments.

Second-order formulas extend first-order formulas with two constructs: applications of relation variables, and second-order quantifiers \(\exists R\), \(\forall R\) over a fresh relation of a given arity. Relation variables are de Bruijn-indexed by a context listing their arities, innermost first. A second-order sentence has an empty relation context and no free element variables. First-order formulas embed into second-order formulas over any relation context. Size counts nodes.

Supply each free relation as its truth-table string. Matrix evaluation uses arithmetic structure reads and tuple indices into these relation tables. Each existential relation quantifier checks that at least \(n^k\) bits remain, takes the next \(n^k\) bits as its new table, and recurses on the rest. At the matrix, require that no certificate bits remain. All operations are total; structure validity is checked separately.

A finite structure \(\mathcal{A}\) over \(V\) consists of:

• a size \(n \ge 2\) and the universe \(\mathrm{Fin}(n)\);

• for each relation symbol of arity \(k\), a \(\mathrm{Prop}\)-valued relation on \(k\)-tuples, that is, on maps \(\mathrm{Fin}(k) \to \mathrm{Fin}(n)\);

• for each constant symbol, an element.

A decidable structure has the same data, with \(\mathrm{Bool}\)-valued relations, and coerces to a structure in which a relation holds where its value is \(\mathrm{true}\). The canonical order \(\le \), the successor relation (\(b = a + 1\)), the minimum \(0\), and the maximum \(n - 1\) of \(\mathrm{Fin}(n)\) are defined for every structure as meta-level helpers. They are not part of the structure, and no formula can mention them.

Simultaneous substitution \(\varphi [\rho ]\) takes a formula with \(m\) free variables and terms \(\rho (0), \dots , \rho (m-1)\) with \(n\) free variables, and replaces each \(x_k\) by \(\rho (k)\), giving a formula with \(n\) free variables. Under a binder, the substitution is lifted: variable \(0\) stays, and every other image is shifted up one de Bruijn index.

Evaluate the interpretation on decidable structures. An arithmetic generator extracts tags by division, coordinates by base expansion, selects a defining relation formula from the fixed finite tag cases, and packs source-constant tuples. The binary map decodes, interprets, and re-encodes; malformed inputs map to \([]\).

For positive \(t,d\), the target universe is \(\mathrm{Fin}(t)\times \mathrm{Fin}(n)^d\), presented on \(\mathrm{Fin}(t n^d)\). A relation of arity \(a\) has a defining formula with \(ad\) variables for each assignment of tags to its arguments. Target constants are tagged tuples of source constants. This full-product construction has no domain restriction or quotient; it follows Senellart–Gnatenko, Section 3.2.

Pullback replaces each free target variable by a tag and a tuple of source terms. Equality compares tags and all coordinates. Quantifiers become finite tag choices followed by coordinate blocks. Composition pulls the outer relation formulas back along the inner interpretation and flattens the nested tuples. This is the tagged full-product case of Immerman, Definition 3.3; constants are source-constant tuples as allowed in its footnote.

A tagged reduction \(P \leq Q\) supplies positive tag and dimension counts, a tagged interpretation \(I\), and \(P(\mathcal A)\iff Q(I(\mathcal A))\) for every source structure. Reducibility is existence of such a witness. Identities, composites, and complementary reductions are explicit witnesses. On one vocabulary this relation defines a preorder; the API also supports reductions across vocabularies.

At cardinality \(n\), require \(n\ge 2\), total length \(\ell _V(n)\), header bits \(1^n0\), and exactly one true bit in every constant block. Express the latter as: for each constant there is an \(a{\lt}n\) such that every \(b{\lt}n\) has block bit equal to the truth value of \(a=b\). Relation-table bits are unrestricted.

A vocabulary has \(r\) relation symbols, indexed by \(\mathrm{Fin}(r)\), each with an arity in \(\mathbb {N}\), and \(c\) constant symbols, indexed by \(\mathrm{Fin}(c)\). It is relational if \(c = 0\). The graph vocabulary has one binary relation symbol and no constants.

\(\mathsf{DSPACE}(S)\) is the class of languages decided by some DTM, with any number of work tapes, in space \(f\) for some \(f = O(S)\).

For \(T \colon \mathbb {N} \to \mathbb {N}\), \(\mathsf{DTIME}(T)\) is the set of languages \(L\) for which there are a deterministic machine with some number \(k\) of work tapes and a function \(f\) with \(f = O(T)\) such that the machine decides \(L\) within time \(f\): on every input \(x\) it halts within \(f(|x|)\) steps with \(1\) in output cell \(1\) (the first cell after \(\triangleright \)) if \(x \in L\) and \(0\) there otherwise. Here \(f = O(T)\) means that \(f(n) \le C \cdot T(n)\) for some real constant \(C\) and all sufficiently large \(n\).

An \(n \times n\) Boolean matrix (the adjacency matrix of a directed graph on \(n\) vertices) corresponds bijectively to a bit string in \(\{ 0,1\} ^{n \cdot n}\) by row-major serialization, entry \((i, j)\) at position \(n i + j\). In particular there are exactly \(2^{n \cdot n}\) such matrices. No module of the library uses this codec yet.

\(\mathrm{bin}(v)\) is the minimal binary expansion of \(v \in \mathbb {N}\), least significant bit first, with \(\mathrm{bin}(0)\) empty. The decoder accepts a string only if it is the minimal expansion of its value, so representations with trailing high zeros are rejected. The code is not prefix-free; an enclosing framing layer fixes the field boundary.

\(\mathrm{toList}(x) = [x_0, \dots , x_{n-1}]\) serializes in increasing index order; \(\mathrm{ofList}\) reads a list whose length is proved to be \(n\); and \(\mathrm{toTotal}(x) : \mathbb {N} \to \{ 0,1\} \) extends \(x\) by \(0\) outside its range. The variable-length correspondence \(\{ 0,1\} ^* \simeq \Sigma _n \{ 0,1\} ^n\) is Mathlib’s.

\(\{ 0,1\} ^{a+b} \simeq \{ 0,1\} ^a \times \{ 0,1\} ^b\) splits a string into its length-\(a\) prefix and length-\(b\) suffix, with concatenation as the inverse, and \(\{ 0,1\} ^{kT} \simeq (\{ 0,1\} ^T)^k\) splits it into \(k\) blocks in row-major order: block \(i\) is positions \(iT, \dots , iT + T - 1\). For an event \(E \subseteq \{ 0,1\} ^T\) and \(w \in \{ 0,1\} ^{kT}\), \(\# _E(w)\) is the number of blocks of \(w\) lying in \(E\).

A raw circuit is a list of gates, each an AND or OR of two absolute wire indices with a negation flag on each input. At arity \(N\), wires \(0, \dots , N-1\) are the inputs and gate \(i\) produces wire \(N + i\); the raw circuit is well formed if it is nonempty and gate \(i\) reads only wires below \(N + i\). A raw circuit is encoded as its gate count in terminated unary (\(m\) ones, then a zero) followed by its gates, each gate as an operation bit (\(1\) for AND), two negation bits, and its two input wire indices in terminated unary. The code \(\mathrm{code}(C)\) of a single-output circuit \(C\) over the fan-in-two AND/OR basis is the encoding of the raw circuit formed by its internal gates in order followed by its output gate. The raw evaluator computes the wires in order in a memo array and returns the last gate’s value, failing on an empty gate list or on a reference to a wire not yet computed. \(\mathrm{evalCode}(N, w, x)\) fails unless \(|x| = N\); otherwise it decodes \(w\) exactly (rejecting malformed codes and trailing bits) and runs the raw evaluator on \(x\).

A binary codec for a type \(\alpha \) with a size measure \(\| \cdot \| \) consists of an encoder \(e : \alpha \to \{ 0,1\} ^*\), a partial decoder \(d : \{ 0,1\} ^* \to \alpha \cup \{ \bot \} \), the round trip \(d(e(a)) = a\), canonicity (\(d(w) = a\) implies \(w = e(a)\)), and an explicit size bound \(|e(a)| \le s(\| a\| )\). The existing rose-tree encodings (Definition 73) give injectivity only, with no decoder at the level of \(\alpha \) and no size bound.

From codecs for \(\alpha \) and \(\beta \), the product codec encodes \((a, b)\) as \(\langle e_\alpha (a), e_\beta (b) \rangle \), with \(|e(a, b)| = 2|e_\alpha (a)| + 2 + |e_\beta (b)|\), and the tagged-sum codec prefixes one tag bit. Both satisfy the codec laws.

A rose tree is a finite list of rose trees; the size of a node with children \(d_1, \dots , d_m\) is \(2 + \sum _i \mathrm{size}(d_i)\). A tree is serialized as balanced brackets: \(0\) opens a node, its children follow in order, and \(1\) closes it. A stack-based parser \(\mathrm{fromBits}\) returns a tree or fails. A type with an injective map into rose trees (instances exist for rose trees themselves, Booleans, natural numbers, lists, options, and products) gets a bit-string encoding by composing with this serialization. This layer supports the rose-tree machine model.

The block of \(x = x_1 \cdots x_n\) is \(\mathrm{delimit}(x) = x_1 x_1\, x_2 x_2 \cdots x_n x_n\, 0 1\): every bit is doubled and the separator \(01\) ends the block. The parser \(\mathrm{unpair?}\) reads one block off the front of a string and returns the payload and the remaining suffix, or fails on malformed input; \(\mathrm{undelimitBlocks}\) parses a string that consists entirely of blocks into the list of their payloads, or fails. The total helpers used by machines are: \(\mathrm{undelimitBlock}\), the payload of the leading block (empty on malformed input); \(\mathrm{takeFirstBlock}\), the leading block itself, framing included (empty on malformed input); \(\mathrm{hasBlock}\), whether the string begins with a well-formed block; and \(\mathrm{tagBlock}(z)\), which is \(1z\) if \(\mathrm{hasBlock}(z)\) and the empty string otherwise.

For a finite event \(E \subseteq \{ 0,1\} ^T\), \(\Pr [E] = |E| / 2^T \in \mathbb {Q}\).

From a codec for \(\alpha \), a codec for lists over \(\alpha \) that frames each element as a block, with \(|e([a_1, \dots , a_m])| = \sum _i (2|e(a_i)| + 2)\).

Canonical codecs, with explicit length bounds, for finite functions (truth tables), machine states, configurations of time-bounded runs, and bounded interaction transcripts. (Internal fixed-width layouts of machine states and of bounded configuration windows, Complexity.qCodec and Complexity.codeCodec, have exact widths but total, non-canonical decoders.)

For \(f \in \{ 0,1\} ^k\), \(\mathrm{maj}(f) = 1\) if and only if more than \(k/2\) positions of \(f\) are \(1\) (strict majority). For \(w \in \{ 0,1\} ^{kT}\), \(\mathrm{maj}_E(w) = 1\) if and only if \(2\, \# _E(w) {\gt} k\).

\(\pi _1\) reads doubled bits until the separator (returning the bits read so far on malformed input), and \(\pi _2\) returns the suffix after the first block, or the empty string if there is no valid block. Both are total.

For a machine \(N\) with \(n\) work tapes, \(\mathrm{rep}(N, k, T)\) has \(k(n+1)\) work tapes and performs \(k\) sequential runs of \(N\) for exactly \(T\) steps each, each run on a fresh bank of \(n + 1\) work tapes (the last simulating the output tape). Two setup transitions precede the first run. After each run it rewinds the input tape and the run’s bank in exactly \(T + 1\) transitions and records the run’s verdict in one more; after the last run it writes the strict majority of the \(k\) verdicts to its output tape (so for \(k = 0\) it writes \(0\)). Every run occupies exactly \(2T + 2\) transitions whether or not \(N\) halts early, so the total time is \(2 + k(2T + 2)\), and simulated step \(t\) of run \(j\) uses the choice bit at the fixed position \(2 + j(2T + 2) + t\). The compact seed of a choice sequence is the \(kT\) bits at those positions, and the accepting event of \(N\) on \(x\) is the set of \(r \in \{ 0,1\} ^T\) along which \(N\) on \(x\) halts with output cell \(1\) equal to \(1\).

\(\mathsf{ZPP}_{\mathrm{LV}}\) is the class of languages \(L\) with a probabilistic machine \(N\) and a polynomial \(T\) such that every trace on every input \(x\) halts within \(T(|x|)\) steps with output either the correct verdict \([x \in L]\) or a designated “don’t know” answer, and the probability of “don’t know” is at most \(1/2\). (The textbook expected-polynomial-time formulation needs an expected-time machine semantics, which the library does not have.)

\(\mathsf{EXP} = \bigcup _{k} \mathsf{DTIME}(2^{n^k})\) and \(\mathsf{NEXP} = \bigcup _{k} \mathsf{NTIME}(2^{n^k})\).

\(\mathsf{FL}\) is the class of functions \(\{ 0,1\} ^* \to \{ 0,1\} ^*\) computed by a DTM in space \(S\) for some \(S = O(\log n)\). The output is unbounded in length and one-way. \(\mathsf{FNL}\) is the class of polynomially balanced relations whose pair language is in \(\mathsf{L}\), and \(\mathsf{TFNL}\) consists of the relations in \(\mathsf{FNL}\) that are total: every \(x\) has some \(y\) with \(R(x, y)\).

\(\mathsf{FNP}\) is the set of polynomially balanced relations \(R\) with \(\mathrm{pairLang}(R) \in \mathsf{P}\). \(\mathsf{TFNP}\) is the set of \(R \in \mathsf{FNP}\) such that every \(x\) has some \(y\) with \(R(x, y)\).

\(\mathsf{FP}\) is the set of functions \(f \colon \{ 0,1\} ^* \to \{ 0,1\} ^*\) for which some deterministic machine computes \(f\) within time \(T\) with \(T = O(n^d)\) for some \(d\): on every input \(x\) it halts within \(T(|x|)\) steps with \(f(x)\) written on the output tape, that is, output cells \(1, \ldots , |f(x)|\) hold the bits of \(f(x)\) and cell \(|f(x)| + 1\) is blank.

A tensor \(T \in A \otimes B \otimes C\), with \(A = \mathbb {C}^\alpha \), \(B = \mathbb {C}^\beta \), \(C = \mathbb {C}^\gamma \) for finite \(\alpha , \beta , \gamma \), is given by its coordinates \(T_{ijk}\). It has rank at most \(r\) if it is a sum of \(r\) outer products \(u \otimes v \otimes w\), and border rank at most \(r\) if it lies in the closure of the set of tensors of rank at most \(r\); \(\mathbf{R}(T)\) and \(\underline{\mathbf{R}}(T)\) are the least such \(r\). Matrices \(X, Y, Z\) act on the three factors by \(X \otimes Y \otimes Z\).

Index \(m = 2k + 1\) slices by their offsets \(-k, \dots , k\). For a block length \(L \ge 1\), the \(i\)-th positive block consists of the slices with offset in \([iL + 1, (i + 1)L]\) and the \(i\)-th negative block of those with offset in \([-(i + 1)L, -(iL + 1)]\); the offsets \(1, \dots , k\) of each sign split into runs of length \(L\), the last possibly shorter. A block \(B\) is good for a set \(S\) of surviving slices if \(|S \cap B| \ge R\). The width of a positive cluster at offset \(r\) paired with a negative cluster at offset \(-s\) is

A function \(\mathrm{LB}\) on sets of slices satisfies the paired-cluster hypothesis with constants \(D\) and \(E\) if, whenever a positive block and a negative block are both good for \(S\), some offsets \(r\) in the positive block and \(-s\) in the negative block satisfy \(D (\Phi _m(r, s) - E) \le \mathrm{LB}(S)\).

For an odd core dimension \(d=2k+1\), set \(L_p=(p+1)(3^{2p}+1)\), \(A_p=L_p+1\), and \(M_p=pL_p+1\). Search the integers \(1\le p\le \lfloor \log _2d\rfloor \) for the largest satisfying

Use the periodic tensor with periods \((A_p,M_p)\), or the zero tensor if no candidate exists. At ambient dimension \(m\), choose \(k=\lfloor (m-1)/2\rfloor \) and pad the odd core by zeros. This defines one computable nonnegative-integer-entry family \(T_m\), independent of any requested approximation parameter.

A parameterized problem is a language \(L\) with a polynomial-time parameter \(\kappa \). It is in \(\mathsf{FPT}\) if it is decidable in time \(g(\kappa (x)) \cdot |x|^{O(1)}\) for some computable \(g\). An fpt-reduction preserves membership, runs in fpt time, and bounds the target parameter by a function of the source parameter. \(\mathsf{W[1]}\) is the closure of \(k\)-Clique under fpt-reductions. First targets: Vertex Cover is in \(\mathsf{FPT}\) by a \(2^k\)-branching algorithm, and \(k\)-Clique is \(\mathsf{W[1]}\)-complete by definition, with \(k\)-Independent Set equivalent to it.

Order the basis \(a_i\) of \(A\) and let \(e_I = a_{i_1} \wedge \dots \wedge a_{i_p}\) for \(I = \{ i_1 {\lt} \dots {\lt} i_p\} \), so that \(a_i \wedge e_I = (-1)^{|\{ x \in I : x {\lt} i\} |} e_{I \cup \{ i\} }\) for \(i \notin I\). The Koszul flattening \(T_A^{\wedge p} \colon \Lambda ^p A \otimes B^* \to \Lambda ^{p+1} A \otimes C\) sends \(e_I \otimes b_j^*\) to \(\sum _{i,k} T_{ijk} (a_i \wedge e_I) \otimes c_k\) (Landsberg and Michałek, Towards finding hay in a haystack, Theory of Computing, 2025, Section 4.1).

These definitions come from the imported algebraic-circuits library. A De Morgan formula on \(n\) inputs is a binary tree whose leaves are literals \(x_i\) or \(\lnot x_i\) or Boolean constants and whose internal nodes are binary AND or OR gates. A protocol on \(n\) inputs is a binary tree whose leaves each name a coordinate \(i {\lt} n\) and whose internal nodes are each owned by Alice or by Bob and branch by an arbitrary Boolean function of the owner’s whole input in \(\{ 0,1\} ^n\); on inputs \(x\) for Alice and \(y\) for Bob it outputs the coordinate at the leaf it reaches. For both, the depth is the length of a longest root-to-leaf path (a leaf has depth \(0\)) and the size is the number of leaves, constant leaves included. A protocol solves the game on a rectangle \(A \times B\) if its output \(i\) satisfies \(x_i \neq y_i\) for all \(x \in A\) and \(y \in B\); it solves the Karchmer–Wigderson game of \(f : \{ 0,1\} ^n \to \{ 0,1\} \) if it solves the game on \(f^{-1}(1) \times f^{-1}(0)\). The minimum formula depth and size of \(f\) (over formulas computing \(f\) at every input) and the minimum protocol depth and size of its game are infima in \(\mathbb {N} \cup \{ \infty \} \), equal to \(\infty \) when no formula or protocol exists.

Let \(m = 2k + 1\). For coefficients \(\gamma \), the tensor \(T_k(\gamma ) = \sum _{i, j} \gamma _{i, j}\, a_i \otimes b_j \otimes c_{i + j}\) in \(\mathbb {C}^m \otimes \mathbb {C}^m \otimes \mathbb {C}^m\), with \(i \in [-k, k]\) and \(j, i + j \in [0, m)\), is the family of Landsberg and Michałek, Towards finding hay in a haystack, Theory of Computing, 2025, (1.1): its slice \(i\) is a weighted shift matrix supported on the diagonal of offset \(i\). The weighted tensor has the explicit coefficients \(\gamma _{a, j} = 2^{2^{a m + j}}\), where \(a = i + k\). A cluster is a choice of \(2p + 1\) slices, with offsets \(o_0, \dots , o_{2p}\); projecting the first factor onto them gives the cluster tensor, with \(2p + 1\) slices. The spread of the offsets is the largest minus the smallest of the sums \(\sum _{t \in K} o_t\) over the subsets \(K\) of size \(p\) or \(p + 1\); the \(p\)-subset spread is the same over the subsets of size exactly \(p\).

\(f \in \mathsf{FP}\) is one-way (against nonuniform adversaries) if for every family of polynomial-size circuits \((A_n)\), the function \(n \mapsto \Pr _{x \in \{ 0,1\} ^n}[f(A_n(f(x))) = f(x)]\) is negligible.

Let \(T\) be a tensor with \(m = 2k + 1\) slices. The property \(\mathrm{PK}_T(p, L, E)\) says: for every set \(S\) of slices and every two clusters \(c^+\) and \(c^-\) of \(2p + 1\) slices of \(S\) in increasing order, each with pairwise distinct \(p\)-subset sums of offsets and diameter at most \(L\), with the offsets of \(c^+\) in \([1, k]\) and those of \(c^-\) in \([-k, -1]\), and with medians \(r\) and \(-s\),

It is the interface between the paired-cluster certificate and the deletion game. For the weighted Landsberg–Michałek tensor \(T_k\) it is written \(\mathrm{PK}(k, p, L, E)\).

For \(A, M \ge 1\) the periodic Landsberg–Michałek tensor is \(T_k(\gamma )\) with the coefficients \(\gamma _{a, j} = 2^{2^{(a \bmod A) M + (j \bmod M)}}\). The exponent codes the position \((a, j)\) only modulo \((A, M)\).

A family \(G_m : \{ 0,1\} ^{\ell (m)} \to \{ 0,1\} ^m\) is a pseudorandom generator with seed length \(\ell \) if two conditions hold:

• for every \(m\) and every circuit \(C\) of size at most \(m\) on \(m\) inputs, \(\lvert \Pr _s[C(G_m(s)) = 1] - \Pr _u[C(u) = 1] \rvert {\lt} 1/10\);

• \(G_m\) is computable in time \(2^{O(\ell (m))}\).

A deterministic protocol for \(f : X \times Y \to Z\) is a binary tree. Each internal node is owned by Alice, who branches on a function of \(x\), or by Bob, who branches on a function of \(y\). Each leaf is labelled by an output. The cost is the depth, and \(D(f)\) is the minimum cost of a protocol computing \(f\). Only the protocols of Karchmer–Wigderson games are formalized (Definition 1374); their leaves name a coordinate, and they solve a relation rather than compute a function.

A tensor \(T \in A \otimes B \otimes C\) is tight if there are weights \(\tau _A \colon \alpha \to \mathbb {Z}\), \(\tau _B \colon \beta \to \mathbb {Z}\), \(\tau _C \colon \gamma \to \mathbb {Z}\) with \(\tau _A\) injective and \(\tau _A(i) + \tau _B(j) + \tau _C(k) = 0\) whenever \(T_{ijk} \ne 0\). Landsberg and Michałek (Definition 2.2) also ask \(\tau _B\) and \(\tau _C\) to be injective, so a tensor that is tight in their sense, in its tight basis, is tight here. For \(S \subseteq \alpha \), \(T|_S\) keeps the slices \(T_i\) with \(i \in S\) and zeroes the others: the restriction of \(T\) to \(\operatorname {span}\{ a_i^* : i \in S\} \subseteq A^*\) (their Definition 2.1), kept inside \(A \otimes B \otimes C\). For \(u \in A\), \(\Pi _u = 1 - (u^* u)^{-1} u u^*\) is the orthogonal projection onto \(u^\perp \).

Fix a field \(\mathbb {F}\). An arithmetic circuit is a DAG with \(+\) and \(\times \) gates over variables and field constants. \(\mathsf{VP}\) is the class of polynomial families \((f_n)\) with \(\mathrm{poly}(n)\) variables and degree, computed by \(\mathrm{poly}(n)\)-size arithmetic circuits. \(\mathsf{VNP}\) is the class of families \(f_n(x) = \sum _{e \in \{ 0,1\} ^{m(n)}} g_n(x, e)\) with \((g_n) \in \mathsf{VP}\) and \(m\) polynomial.

Map a QBF to an expression over \(\mathbb {F}\): \(\neg a \mapsto 1 - a\), \(a \wedge b \mapsto ab\), \(\forall x\, \varphi \mapsto \varphi |_{x=0} \cdot \varphi |_{x=1}\), \(\exists x\, \varphi \mapsto 1 - (1 - \varphi |_{x=0})(1 - \varphi |_{x=1})\), interleaved with linearization operators \(L_{x}\, p = (1 - x)\, p|_{x=0} + x\, p|_{x=1}\) that keep every intermediate polynomial of individual degree at most \(2\).

A constraint graph over an alphabet \(\Sigma \) has vertices \(\{ 0, \dots , V - 1\} \) and finitely many indexed directed edges (parallel edges and self-loops allowed), each carrying a Boolean-valued binary constraint on the labels of its tail and head. It is satisfiable if some labelling of the vertices satisfies every edge. For finite nonempty \(\Sigma \), its unsatisfiability value is the least, over all labellings, of the fraction of edges left unsatisfied (taken to be \(0\) for an edgeless graph); it is \(0\) exactly when the graph is satisfiable.

A function \(r\) is constructible if \(x \mapsto 1^{r(|x|)}\) is in \(\mathsf{FP}\).

For \(0 \le s {\lt} c \le 1\) and fixed arity and alphabet, \(\mathrm{Gap}_{c,s}\)-CSP is the promise problem whose yes-instances are encoded constraint systems with value at least \(c\) and whose no-instances have value less than \(s\). \(\mathrm{Gap}\)-MAX-3SAT\(_{1,s}\) separates satisfiable 3CNFs from those in which every assignment satisfies fewer than an \(s\) fraction of the clauses.

\(\mathsf{IP}(c, s)\), \(\mathsf{MA}(c, s)\) and \(\mathsf{AM}(c, s)\): the classes with completeness \(c\) and soundness \(s\) as parameters, together with monotonicity in both thresholds and the identification of the hard-wired classes with \(c = 2/3\), \(s = 1/3\).

A label-cover instance is a bipartite constraint graph with label sets \(\Sigma _A\), \(\Sigma _B\) whose constraints are projections \(\pi _e : \Sigma _A \to \Sigma _B\); its value is the largest fraction of edges satisfied by a labelling.

For \(f : \{ 0,1\} ^m \to \mathbb {F}\), the multilinear extension \(\widetilde{f}(x) = \sum _{b \in \{ 0,1\} ^m} f(b) \prod _i (b_i x_i + (1 - b_i)(1 - x_i))\), with the facts that it agrees with \(f\) on the cube and is the unique multilinear polynomial doing so.

A PCP verifier is non-adaptive: it has a list of proof positions (natural numbers) for each input \(x\) and coin string \(r\), together with an \(\mathsf{FP}\) function mapping \(\mathrm{pair}(x, r)\) to the rose-tree serialization of that list, and a verdict language in \(\mathsf{P}\) that decides \(\mathrm{pair}(\mathrm{pair}(x, r), a)\), where \(a\) lists the bits of the proof (a finite bit string) found at those positions. A position past the end of the proof reads as \(0\). The verifier is query-bounded by \(q\) if it reads at most \(q(|x|)\) positions for every \(x\) and every coin string \(r\).

A transcript is a list of messages (bit strings); the verifier speaks at even positions and the prover at odd ones. A prover strategy is an arbitrary function from the visible transcript to the next message; it never sees the verifier’s coins, and it is bounded by \(m\) if the message it returns on every transcript has length at most \(m\). A protocol consists of a round count, a coin count \(c\) and a message-length bound (functions of the input length), a next-message function in \(\mathsf{FP}\) applied to the encoded view \(\mathrm{pair}(\mathrm{pair}(x, r), \langle \tau \rangle )\) of the input \(x\), the private coins \(r\) and the transcript \(\tau \) (where \(\langle \tau \rangle \) is the rose-tree serialization of \(\tau \)), a proof that for every \(x\), \(r\) and \(\tau \) the verifier’s message has length at most the message bound at \(|x|\), and a verdict language in \(\mathsf{P}\). Each round appends the verifier’s message, computed from the current view, and then the prover’s reply to the transcript extended by that message. The verifier accepts if the view of the transcript after the round count at \(|x|\) many rounds lies in the verdict language, and the accept event is the set of coin strings \(r \in \{ 0,1\} ^{c(|x|)}\) on which it accepts.

For a polynomial \(g\) in \(m\) variables over \(\mathbb {F}\) with individual degree at most \(d\), given by an evaluation oracle, and a claimed value \(v\) of \(\sum _{b \in \{ 0,1\} ^m} g(b)\): in round \(i\) the prover sends a univariate polynomial \(h_i\) of degree at most \(d\), the verifier checks \(h_i(0) + h_i(1)\) against the current claim, and replaces the claim by \(h_i(r_i)\) for a random \(r_i \in \mathbb {F}\); at the end it checks \(g(r_1, \dots , r_m)\) against the last claim.

\(L \in \mathsf{IP}\) if some protocol whose round count, coin count \(c\) and message bound \(m\) are given by polynomials with natural-number coefficients satisfies: for \(x \in L\) some strategy bounded by \(m(|x|)\) is accepted with probability at least \(2/3\), and for \(x \notin L\) every strategy bounded by \(m(|x|)\) is accepted with probability at most \(1/3\), the probability being over uniform \(r \in \{ 0,1\} ^{c(|x|)}\). The counts are required to be polynomials, not merely polynomially bounded, so that the verifier can compute them.

For a deterministic machine \(U\) (with any number of work tapes), a string \(x\) and a clock \(t\),

with values in \(\mathbb {N} \cup \{ \infty \} \) and value \(\infty \) when no program exists. Here “produces” means halting with exact output \(x\) (Definition 13), and “within \(t\) steps” means halting after at most \(t\) transitions. No universality is assumed. A prefix-free variant \(K_U\) is defined only for machines bundled with a proof that their halting domain is prefix-free (TM.PrefixFreeMachine); it is the plain minimum \(C_U\) of the certified machine.

\(\mathsf{L}\) is the class of languages decided by a deterministic transducer, with any number of work tapes, in space \(f\) for some \(f = O(\log n)\).

A language is a set of finite binary strings, \(L \subseteq \{ 0,1\} ^*\).

A negation-normal unbounded formula over \(N\) variables is a tree built from constants, literals, and AND and OR gates of any fan-in; an empty AND is true and an empty OR is false. Its size counts all nodes (constants, literal occurrences, and gates), and its depth counts gates on a longest root-to-leaf path.

A multigraph is acyclic when some numbering of its vertices increases strictly along every edge, from its first endpoint to its second. A finite multigraph is acyclic exactly when no vertex reaches itself along a directed walk of positive length.

Run both actual advice programs on the original factored sample \((Z,B,A)\). The retained law is \(((Z,B,W'),W)\), where \(W,W'\) are the honest and tampered outputs after the additional final extraction. Thus the whole original right state remains, including both right inputs when these are arbitrary functions of \((Z,B)\). For advice length \(a\) and original left-envelope total \(\alpha \), define

The proof witness records a finite deterministic transcript of the original sample, its exact normalized left and right kernels, and pointwise equality of both current states with the executed programs. It bounds the original-source envelope totals by \(\alpha ,\beta \) and the honest-state discrepancy given the transcript by \(\rho \). Once the advice prefixes differ, the transcript fixes the tampered current state. Normalized original factors, nonnegative source envelopes, and an initial whole-state discrepancy construct the empty-prefix witness. This is internal proof data, not a security premise for the eventual public correlation-breaker theorem.

For left input length \(n\), advice length \(a\), target exponent \(t\), and requested output \(o\), set

The total chooser uses \(m\) both as source entropy reserve and intended right-source length. Capacity \(m\le n\) remains an explicit condition.

Initialize the right state from a prefix of \(y\), completed with false bits when short. Fold the actual flip-flop step over the advice bits in their given order, holding \(x,y\) fixed. This is the loop in Chattopadhyay–Goyal–Li Algorithm 2. The present construction additionally applies the depth-24 extractor to \(x\) using the final state’s seed prefix. The encoded runtime stores the sources, unary parameters, remaining advice, and current state explicitly.

For \(K,J,D,C,\varepsilon \) as above, put

Set \(\rho _0=\rho \) and \(\rho _{i+1}=\Phi (\rho _i,D^{8i}\alpha ,C^{5i}\beta )\). The common update conservatively covers all three step estimates.

Decode \(\operatorname {pair}(\operatorname {pair}(x,y), \operatorname {pair}(\alpha ,\operatorname {pair}(t_{\rm word},o_{\rm word})))\). The last two word lengths are the target and output parameters. Compute the selected \(e,L,m\), normalize \(y\) to its first \(m\) bits with false completion, then execute the actual advice program and return its requested output prefix. Zero requested width returns immediately.

Return the first \(o\) coordinates of each actual output, completing positions beyond the full width \(d\) by false. Retain the original \((Z,B)\) and the truncated tampered output. This is a total definition for all widths; the uniformity guarantee below concerns \(o\le d\).

Execute the actual first phase and then the actual four-call round repeatedly, always on the same original source words. The selected construction runs \(R=\lceil \log _2(t+1)\rceil \) rounds and uses the first-phase chooser at target \(\sigma =\mathrm{target}+R+1\). Its retained law is the direct image of the original factored source law, keeping the original tag, full right state, and selected tampered outputs alongside the honest output. The selected string evaluator computes these parameters and normalizes the original right word before running the construction.

Sample \((Z,A,B)\) from a factored law. A left source \(x(Z,A)\) and right seed \(y(Z,B)\) give the retained law of \((Z,B,E(x(Z,A),y(Z,B)))\). The affine version first combines the left source with a right mask \(m(Z,B)\) using a specified operation, and applies the same extractor and actual seed. Both are deterministic images of the original factored law and retain the whole right variable.

An actual state consists of the transcript weight, normalized-factor candidates, unchanged original source maps, and left/right row contributions. It carries no extraction certificate. Each transition executes the five observations of one round and lifts the original source maps along the old-transcript projection. The invariant at capacity \(k\) and error \(\rho \) bounds the honest left row’s discrepancy from uniform while retaining every subset of at most \(k\) tampered rows.

Set \(R=\lceil \log _2(t+1)\rceil \) and \(\sigma =\mathrm{target}+R+1\). Evaluate the unchanged first-phase chooser at \(\sigma \), writing its widths as \(L_0,L,D\), its original-left entropy reserve as \(\kappa \), and its local error exponent as \(e=\sigma +3\). The original-left reserve for the complete construction is \(2\kappa \). Write \(m_0=2^{64}L_0\), \(c_0=2^{24}L_0\), and \(c=2^{24}L\). The initial transcript losses are \(A_x=(t+1)m_0\) and \(A_y=(t+1)(c_0+m_0+c)\); one short-message family costs \(M=(t+1)c\) bits. The remaining source entropies before round \(i\) are \(2\kappa -A_x-2iM\) and \(D-A_y-4iM\).

Write \(F\) for the complete selected affine construction, with seed width \(d\), source reserve \(k\), and error \(2^{-q}\). Fix advice \(\alpha _0,\ldots ,\alpha _t\) and deterministic source observations \(L_0,\ldots ,L_t\) of width \(d\). The actual leaky law retains all \(F(A+b,y_i\oplus L_i(A),\alpha _i)\) for \(i{\gt}0\), together with the honest output \(F(A+b,y\oplus L_0(A),\alpha _0)\). An honest seed is bad at threshold \(\gamma \) if some shift and tampered seed tuple give conditional-uniformity distance greater than \(\gamma \). The complete leakage reserve is \(k+(t+1)d\).

Follow the three-stage first phase of Chattopadhyay–Liao, Theorem 6.1, https://arxiv.org/abs/2110.12652. On the same masked source \(X=A+B\), first extract linearly with a prefix of the right input, run the actual advice breaker with the source/seed roles reversed, and extract linearly again using its output. Index the honest execution by \(\mathsf{none}\) and the \(t\) tampered executions by \(\mathsf{some}(i)\). The transcript records all initial prefixes and mask contributions, all first extraction outputs, then all advice outputs. It retains the original latent variables in its factored representation. These total definitions alone assert no statistical guarantee.

For one tampered index \(i\), the second-seed law retains the first right message, complete original left state, and tampered advice output. The final pair laws retain the entire executed transcript, original right state, and corresponding tampered final value. One law contains the original-left extraction contributions; the other contains the actual masked program outputs. Set \(r_0=2^{64}L_0\), \(r=2^hL_1\), \(F=2^{2h+14}L_1\), and \(M=\sum \mu \). Their complete error budget is

where \(e_1^*\) is the requested error exponent of the advice call, whose internal exponent is selected by its checked error schedule.

For source width \(n\), tampering count \(t\), advice length \(a\), and target error exponent \(s\), set

Use \(h=\lceil \log _2(t+1)\rceil +64\), local target \(e=s+3\), and

The advice call uses its checked internal error schedule for target \(e\). These explicit conservative choices do not assert the paper’s sharp constants or universal capacity \(k\le n\).

False-complete the first seed prefix, perform the first depth-64 extraction, run the actual advice program with reversed input roles, and feed its output to the growing-depth final extraction on the same supplied source word. The paired evaluator reads three data words and six unary numerical words. Each component keeps its total behavior on invalid inputs.

Derive \(n\) and \(a\) from the supplied source and advice word lengths. With unary \(t,s\), compute the complete chooser, truncate or false-complete the right word to its chosen width \(d\), and run all three actual calls. The paired input stores source, right, and advice words followed by the two unary parameter words. No source-entropy or capacity test is performed.

Starting with a long row, use its short prefix to extract from the original right word, use that seed to extract a short row, reread the original right word with this short row, then extract the next long row from the unchanged original affine input \(X=A\mathbin {\oplus }B\). The proof tracks its left contribution and right mask separately. All calls are actual matched extractors. The transcript observes right prefix masks, actual prefixes, the first right seeds and short-row mask contributions, actual short rows, then the second right seeds. This is the round in Chattopadhyay–Liao, Theorem 6.1, printed pp.23–25.

Put \(c=2^{24}L\), \(m=2^hL\), \(k_{24}=2^{62}L\), and \(k_h=2^{2h+14}L\). For \(s=|S|\), \(u=|S\cup T|\) and original source envelope totals \(\alpha ,\beta \), define

Each law reads only actual original inputs and executed calls. The final left and masked output laws retain the complete transcript, original right state, and selected tampered outputs. Intermediate seed laws are the exact conditional marginals needed by the next call; no security property or replacement-source witness is a definition.

Decode \(\operatorname {pair}(\operatorname {pair}(x,\operatorname {pair}(y,w)), \operatorname {pair}(t_{\rm word}, \operatorname {pair}(L_{\rm word},e_{\rm word})))\). The three parameter-word lengths specify \(t,L,e\). False-complete the old row’s short prefix and execute the four component string programs, rereading the original source words. The final depth is \(h=\lceil \log _2(t+1)\rceil +64\).

At each outer coordinate, XOR all component bits obtained by applying the correlation breaker to the same original source, the sampler’s candidate seed, and the candidate advice. This is a deterministic map; statistical and runtime guarantees are separate statements.

A mixed circuit contains arbitrary binary Boolean gates and special gates of the form \(h_j(\prod _i \phi _{ji}(z_i))\), where \(M_j\) is a finite commutative monoid, \(\phi _{ji}:\{ 0,1\} \to M_j\) is a slot-dependent contribution, and \(h_j:M_j\to \{ 0,1\} \) is arbitrary. Fan-in, fanout, depth, repeated slots, and special-to-special connections are unrestricted. For the actual \(q\) special occurrences, define

This counts one output-guess bit and one aggregate register per occurrence. An aggregate network adds local monoid contributions and a final predicate of their product to the Boolean wire constraints of a graph network.

If a mixed circuit has \(s\) binary gates and special registers \(M_j\), its exact capacity is \(B=s+\sum _j\log _2|M_j|\). The integral version rounds each logarithm upward. These capacities have no guessed-output term. A one-way summary for a coordinate split depends only on the sending coordinates and determines the output for every assignment to the remaining coordinates.

Let \(R\) be the product of all special-gate registers. A joint factorization consists of a finite commutative monoid \(M\), a homomorphism \(d:M\to R\), and one contribution \(a(w,b)\in M\) for each circuit wire \(w\) and Boolean value \(b\), such that \(d(a(w,b))\) is exactly the vector of that wire’s contributions to all special gates, counting repeated slots. Its budget is \(D_M=2\lceil \log _2|M|\rceil \).

Observe a right-side message \(V\). Feed the original right-side source and the resulting left-side seed to the actual advice program. Retain the observation, original tag, complete original left state, and actual tampered output.

Read all left seeds and right source copies from the original factored sample. Apply the same extractor to each pair, retaining the original transcript, every executed left seed, and the tampered outputs indexed by \(S\), alongside the honest output.

From the original factored law of \((Z,A,B)\), reveal \(v(Z,B)\) and compute a seed \(s(Z,v(Z,B),A)\). Alternating extraction applies \(E\) to the right source and this seed, retaining \((Z,v(Z,B),A)\). The affine two-call law instead obtains that seed by applying a first extractor to the combined left source and right mask. It retains the whole left state and the first call’s seed and extracted mask.

Set \(b=2^{24}L\) and \(h=\lceil \log _2(d+1)\rceil +64\). For an outer word of width \(8b\) and candidate word of width \(s=\mathrm{gammaBlockSeedBudget}(b)\), use the actual padded Gamma output as the seed of the actual growing matched extractor at error \(1/16\). Read its first \(d\) bits, completing with false bits if needed. Little-endian binary codes enumerate the outer and candidate words; concatenating the codes gives injective advice of length \(8b+s\).

Decode a bit list by polynomial interpretation and the quotient map into \(\mathbb F_2[X]/(M_s)\). Encode a quotient element by the coefficients of its unique reduced representative, retaining exactly \(2\cdot 3^s\) bits. This gives a semantic equivalence with lists of that exact length; it is not an algorithm on abstract quotient objects.

Write \(K_s=\mathbb F_2[X]/(M_s)\) and let \(t\) be its named root. For \(d=3^v\), define \(E_{s,v}(Z)=Z^d-t\) over \(K_s\). The binary quotient \(K_{s+v}\) is identified as an \(\mathbb F_2\) algebra with \(K_s[Z]/(E_{s,v})\).

Over the explicit field \(F_s=\mathbf F_2[X]/(M_s)\) of bit width \(b=2\cdot 3^s\), project to the first \(\ell \) coefficients. The runtime hash multiplies two supplied bit words, reduces modulo the generated binary trinomial, and takes the requested prefix. Its paired evaluator receives source, seed, modulus half-degree, and output count as runtime words. The decoded map uses a canonically encoded field seed.

Set \(M_s(X)=X^{2\cdot 3^s}+X^{3^s}+1\) over \(\mathbb F_2\).

For a coefficient \(a\) in the supplied field, set \(E_{a,s}(X)=X^{3^s}-a\).

The predicate \(\mathrm{BisectionBound}(\xi ,N_0)\) says that every simple \(3\)-regular graph on \(n{\gt}N_0\) vertices has a cut \((S,S^c)\) with \(||S|-|S^c||\le 1\) and at most \((1/6+\xi )n\) crossing edges. The Monien–Preis conclusion for every \(\xi {\gt}0\) and some \(N_0\) is proved in Theorem 461.

Addition XORs the coefficient lists with zero padding. Modular squaring reduces after each square, once per bit in a unary count word; it starts by reducing the dividend. The evaluator reads dividend, modulus, and count through nested pairing. A zero modulus gives the empty output.

Split a coefficient word into consecutive blocks of runtime width \(b\). For a runtime block count \(t\), evaluate the first \(t\) blocks by Horner’s rule from high to low, reducing modulo the supplied binary modulus after every step. Width and count are unary word lengths. Missing bits are zero, and a zero modulus gives empty output.

A bit list represents a polynomial over \(\mathbb F_2\), constant coefficient first, with high zero padding permitted. Carryless multiplication computes the parity of each coefficient convolution. The evaluator reads both operands through the standard pairing codec. Both polynomials are runtime inputs.

Significant length is one past the highest true coefficient, or zero. For a nonzero modulus of degree \(d\), scan the dividend from high to low, keeping \(d\) bits. Shift, insert the next coefficient, and XOR the modulus when needed to cancel the degree-\(d\) term. A zero modulus returns the dividend unchanged, following the polynomial remainder convention. The paired evaluator reads both lists at runtime.

A row-major \(d\) by \(b\) bit matrix is transposed by sending input position \(jb+i\) to output position \(id+j\). The output has exactly \(db\) bits. Absent input bits are false; excess bits are ignored. Both dimensions are supplied as unary word lengths.

Generate \(2d+1\) bits, true exactly at positions \(0,d,2d\). The rounded generator takes \(d=3^{\lceil \log _3 n\rceil }\), where \(n\) is the input word length; at \(n=0\), it takes \(d=1\).

A threshold-\(K\) source on \(t\) blocks is a normalized probability weight on \(\alpha ^t\) for which every one-block prefix extension satisfies \(Kp(u,a)\le p(u)\). This multiplicative definition includes zero-mass prefixes without conditional division. For \(K{\gt}0\) it expresses conditional min-entropy at least \(\log _2K\) in every block given its predecessors.

Split a tuple of \(t\) pairs into \(2t\) coordinates, preserving the order first coordinate, second coordinate, then the next pair. With zero-based indexing, pair \(i\) occupies positions \(2i\) and \(2i+1\). This map is an equivalence and introduces no randomness.

Let \(C\) be the vertex boundary of a side \(S\) and let \(X\subseteq S\setminus C\). The lift of \(X\) is \(X\) together with all vertices of \(C\) adjacent to \(X\). The shared boundary consists of those vertices of \(C\) with at least two neighbors in \(X\). When \(C\) is independent and each of its vertices has one outside neighbor in a cubic graph, each vertex of \(C\) represents a red edge between its two interior neighbors. The shared boundary counts internal red edges, preserving parallel edges as distinct boundary vertices.

Delete designated edges \(F\) and take the connected components of \(B-F\) as quotient vertices. Two distinct components are adjacent when an original black edge joins them. The region-boundary quotient designates the union of all black cuts of a supplied region family.

A multigraph with distinct vertices \(i_1,\dots ,i_n\) (inputs) and \(o_1,\dots ,o_m\) (outputs), \(n+m\) in all, is an \((n,m)\)-concentrator when every set \(X\) of at most \(m\) inputs is joined to some \(|X|\) outputs by \(|X|\) vertex-disjoint directed walks, one from each input of \(X\); the outputs are not prescribed, and the walks may pass through other inputs and outputs. Every path is a walk, so this includes the concentrators of Pinsker (On the complexity of a concentrator, 7th International Teletraffic Congress, 1973), defined with paths. Parallel edges are counted separately.

Push the original factored source law through the concrete three-call look-ahead. Retain \(z\), the full right state, and both honest and tampered first outputs alongside the honest second output.

Let \(e_i(j)=\lfloor j/h^i\rfloor \bmod h\) and \(M_j(z)=\prod _{i{\lt}m}z_i^{e_i(j)}\). For \(K\) coefficient polynomials \(p_j\) define

Only the first \(K\) features are used, where \(K\) will be the actual source cardinality, rather than the full capacity \(h^m\).

The full neighbor of a source \(f\) at seed \(y\in F\) is \((y,((f^{h^i}\bmod E)(y))_{i{\lt}m})\). The neighbors of \(P\) are the union of these pairs over \(f\in P\) and every seed in \(F\).

A vector of \(m\) elements of \(F_s\) is encoded by concatenating its \(m\) canonical blocks of width \(b=2\cdot 3^s\). Decoding reads those blocks in the same order. The resulting equivalence is between coordinate vectors and bit words of length exactly \(mb\), including high zero bits. These semantic maps describe the existing runtime output layout.

Fix a signature and an interpretation of it. The conditional complexity of a target \(f\), possibly with several outputs, given supplied functions \(g_1, \ldots , g_k\) of the same input is the minimum number of gates, every gate counted, of a circuit \(h\) with \(h(x, g(x)) = f(x)\) for every \(x\): the original inputs and the supplied values are free extra inputs, and nothing is required of \(h(x, y)\) when \(y \ne g(x)\). It is \(\infty \) when no circuit computes \(f\) this way.

For a joint law \(p(a,b)\) with first marginal \(p_A(a)\), its conditional row is \(p(a,b)/p_A(a)\) when \(p_A(a)\ne 0\) and uniform otherwise. Uniform extension appends independent uniform randomness to a supplied first-coordinate law. Write \(U_2p(a,b)=p_A(a)/|B|\) for the law retaining the actual first marginal and uniformizing its second coordinate.

For an element \(\omega \) of a field and \(N\in \mathbb {N}\), the Fourier matrix is \(F_N=(\omega ^{rc})_{0\le r,c{\lt}N}\), with rows \(r\) the outputs and columns \(c\) the inputs. When \(\omega \) is a primitive \(N\)-th root of unity, \(x\mapsto F_Nx\) is the \(N\)-point discrete Fourier transform: over \(\mathbb {C}\) with \(\omega =e^{2\pi i/N}\) the classical DFT, for \(N=2^k\) the map computed by the fast Fourier transform, and over \(\mathbb {Z}/q\) with \(N\mid q-1\) a number-theoretic transform.

Four distinct vertices \(a,b,c,d\) form a valid switch when \(ab\) and \(cd\) are edges and \(ac\) and \(bd\) are absent. The switched graph deletes \(ab,cd\) and adds \(ac,bd\).

The runtime inputs are a coefficient word, unary half-degree, unary extension degree, seed word, unary stride, and unary output-coordinate count. Transpose the source coefficient blocks, square modulo the larger generated binary modulus, transpose back, and evaluate the blocks by Horner modulo the base modulus. Coordinate \(i\) uses \(ri\) squarings; concatenate the coordinates.

For semantic comparison, interpret the first \(d\) blocks of width \(b=2\cdot 3^s\) as a source polynomial over \(K_s\). The decoded map canonically encodes a field seed before running the program and decodes each output block. The runtime output omits the seed; strong distributional comparisons retain it externally.

Given a word of concatenated \(n\)-bit blocks, a seed word, a unary block count, and the condenser parameters, apply the scheduled bit program to each fixed-width input slice using the same seed and concatenate the resulting output words in block order.

Given source length \(n\), entropy budget \(k\), inverse-error exponent \(e\), and rate parameter \(u\), set \(T=e+\lceil \log _2(9(n+1)(k+1))\rceil +1\). Retain the sparse choices \(b=2\cdot 3^s\) and \(r=b-T\). Set \(v=\lceil \log _3\max (3,\lceil n/b\rceil )\rceil \), \(d=3^v\), and \(m=\lceil k/r\rceil \), with total natural-number division in degenerate cases. These rounding choices are deductions in this formalization from the credited sparse rate and loss bounds.

Compute the explicit dimensions from \(n,k,e,u\) and run the binary condenser on source and seed words. The paired evaluator takes the four numerical parameters as unary word lengths. The decoded map canonically encodes a field seed and reads the computed coordinates.

If the selected field width is \(b=2\cdot 3^s\) and the condenser has \(c\) field coordinates, set \(H=c3^s\). The paired map runs the actual scheduled bit program on the input and encoded field seed, then reads its first and second \(H\) bits as two Boolean vectors.

Strict majority returns false on ties, including the empty input. The margin on designated good coordinates is their number of true bits minus their number of false bits.

A function is a two-sided flat sumset disperser at threshold \(K\) if both Boolean values occur among the sums of every pair of sources of size at least \(K\). Balanced padding is the \((n+1)\)-bit function \(g(b,x)=b\oplus f(x)\), evaluated on lists by the corresponding tail evaluator followed by XOR with the first bit.

For finite seed and output sets, \(E\) is a flat seeded extractor at threshold \(K\) and error \(\epsilon \) if every uniform source of support at least \(K\), with an independent uniform seed, has output test-set discrepancy at most \(\epsilon \). For each test of density at most \(\epsilon \), an input is bad if more than a \(2\epsilon \) fraction of seeds hit that test. The sampler contract requires bad-input probability at most \(\delta \) for every source with point masses at most \(1/L\). The definition records this cap as \(Lp(x)\le 1\); its entropy interpretation requires \(L{\gt}0\).

For a field \(F\), additive group \(\Omega \), and additive map \(\pi :F\to \Omega \), set \(H(x,a)=\pi (ax)\). The multiplier \(a\) is the hash seed. Coefficient truncation gives the standard field hash of Guruswami–Umans–Vadhan, Lemma 5.1.

Let \(K\) be an algebra over \(F\) with a basis \(b_0,\dots ,b_{n-1}\). Multiplication in \(K\), written in coordinates, is the map \(F^{n+n}\to F^n\) sending the coordinates \(x\) and \(y\) of two elements to the coordinates of their product \(\bigl(\sum _i x_ib_i\bigr)\bigl(\sum _j y_jb_j\bigr)\). The first \(n\) inputs are the coordinates of the first factor and the last \(n\) inputs those of the second.

Set \(N=2^{8b}\), \(C=2^s\), \(a=8b+s\), \(q=54b+s+10\), and \(\gamma =2^{-(17b+10)}\). Let \(d\) be the selected seed width of the fixed affine breaker with \(4C-1\) tamperings. Use the actual enumerated sampler at width \(d\) and the binary advice above, XOR the \(C\) calls at each of the \(N\) outer coordinates, and take their strict majority. The source entropy \(k\) is the maximum of the actual affine leakage reserve and the amplified sampler reserve.

For a finite source support \(P\) and seeded map \(C\), let \(\Gamma _C(P)=\{ (y,C(x,y)):x\in P,\ y\in S\} \). The seeded test probability is the fraction of independent uniform source and seed pairs whose joint seed-output belongs to the test set. Repeated outputs retain their multiplicity in this probability.

Run both look-aheads and both selected refreshes, assuming the old transcript fixes the tampered right input. Retain the full common look-ahead history, selected tampered refresh, and original left state. Each selection bit chooses its second short output exactly when true.

Use the actual depth-24 extractor for \(W\) and \(Q\), and the actual depth-64 extractor \(R\) for refreshing from the original right source \(y\). A look-ahead returns \((r_1,r_2)\) from \(s_1=\operatorname {prefix}_d(q)\), \(r_1=W(x,s_1)\), \(s_2=Q(q,r_1)\), \(r_2=W(x,s_2)\). For advice zero, refresh with \(R(y,r_1)\), perform another look-ahead, and return \(R(y,\bar r_2)\); for advice one, use \(r_2\) and \(\bar r_1\). This is Chattopadhyay–Goyal–Li Algorithm 1, with all eight calls explicit.

For arbitrary honest and tampered advice bits, record both pairs of right states and all eight short look-ahead outputs. Leave both final outputs unobserved. Each becomes a right-only map after fixing this transcript. The factors condition the original sources successively on the two actual look-ahead histories.

Give the runtime an \(8b\)-bit source and a seed of exactly \(r(b)=2^{27}\lceil \log _2(b+1)\rceil ^3\) bits. Read its \(b\) output coordinates to define the Boolean family. This definition invokes the actual total string program, including its specified small-size behavior.

For target \(b\), set \(L=\lceil \log _2(b+1)\rceil \), \(R=\lceil \log _2(L+1)\rceil \), \(h=\lfloor \log _2 b\rfloor -3R-15\) using natural subtraction, \(E=h+4\), and

The guard is \(3R+15\le \lfloor \log _2 b\rfloor \). Use \(N=8b\) input bits and keep the first \(b\) output bits. Output coverage holds even when the guard fails.

Generate the rounded parameters from \(b\) and execute \(h\) levels if the size guard holds, or zero levels otherwise. Return the first \(b\) bits on the guarded branch and \(b\) zero bits otherwise. The single paired string evaluator infers \(b\) as the source-word length divided by eight.

Give each edge \(uv\) of a finite simple graph the Gaussian edge score \(\langle y_{uv},\omega \rangle \) with \(y_{uv}=(\hat a_u+\hat a_v)/\lVert \hat a_u+\hat a_v\rVert \), built from the kernel with decay rate \(q\) and radius \(R\). For \(c{\gt}0\) the band graph keeps the edges scoring in \([-c,c)\), and the band cluster of a vertex is its connected component in the band graph. The band hypothesis \(\mathrm{BandSubcritical}(q,R,c)\) says that for every \(\varepsilon {\gt}0\) some \(K\) makes the expected number of vertices whose band cluster has more than \(K\) vertices at most \(\varepsilon h\) on every simple cubic graph with \(h\) vertices. This is an open percolation hypothesis, not a theorem of the library: it asserts that the band clusters of the edge-score field are subcritical uniformly over cubic graphs. Numerically it holds on the infinite cubic tree for \(c{\lt}0.1826\), which appears to be the worst case.

For a finite simple graph, a decay rate \(q\), and a radius \(R\), the kernel row of a vertex \(v\) is \(a_v(z)=q^{\operatorname {dist}(v,z)}\) when \(\operatorname {dist}(v,z)\le R\) and \(0\) otherwise. Its normalization is \(\hat a_v=a_v/\lVert a_v\rVert \); the norm is at least one because \(a_v(v)=1\).

Read a dividend, a unary half-degree target, and a unary squaring count. Generate the rounded trinomial modulus and run the bounded modular-squaring evaluator on these runtime data.

Write \(H_2(p)=-p\log _2p-(1-p)\log _2(1-p)\) and define

When \(k+3\le n\), the factor \(\alpha (n,k)\) is the probability that two designated distinct primary variables both lie on a uniformly chosen sending side of size \(n-k-1\). The constant \(c\) measures the information saving from a Boolean message whose probability of being true is at most one quarter.

Set \(\eta _2=1-H_2(4/9)\), \(\eta _3=1-H_2(8/27)\), \(\gamma =\log _2(3/2)\), \(c=1-H_2(1/4)\), and \(r=1-H_2(1/8)\). Put

The new exact coefficients and finite penalty are

Put \(c=1-H_2(1/4)\), \(r=1-H_2(1/8)\), \(\rho =H_2(1/4)-1/2\), and \(\beta =H_2(1/4)-3/4\). Define

The scalar and inversion constants are the exact ratios

with inversion penalty \(P_{\mathrm I}=4r/D_{\mathrm i}\). Their decimal approximations are \(C_{\mathrm F}\approx 1.2364849888\), \(C_{\mathrm I}\approx 1.5644077959\), and \(P_{\mathrm I}\approx 0.5640721944\).

Let \(K\) be a binary field and fix a linear isomorphism \(e:\mathbf F_2^n\longrightarrow K\). The Boolean map \(G_e\) encodes its input using \(e\), cubes it in \(K\), and decodes all \(n\) output bits in the same basis.

With \(c=1-H_2(1/4)\), put \(C_{\mathrm G}=(7+4c)/(4+2c)\approx 1.771556\) and \(P_{\mathrm G}=(3+4c)/(4+2c)\approx 0.857781\).

Let \(K\) be a binary field and fix a linear isomorphism \(e:\mathbf F_2^n\longrightarrow K\). The Boolean map \(I_e\) encodes its input using \(e\), takes the multiplicative inverse in \(K\) with \(0^{-1}=0\), and decodes all \(n\) output bits in the same basis.

With binary entropy measured in bits, set

Here \(\beta {\gt}0\) charges distinct primary variables, while \(\rho {\gt}0\) is the gate saving in the joint message bound.

A gate is either an affine Boolean function \(b\oplus \bigoplus _i a_i z_i\), or an optionally negated conjunction \(b\oplus \bigwedge _i[z_i=p_i]\), with arbitrary finite arity and Boolean parameters. Every gate costs one. The existing acyclic circuit model allows arbitrary depth, fanout, and repeated wires, including opposite literals of the same wire. This basis contains unbounded AND, OR, and XOR, constants, and every binary Boolean operation; binary normalization preserves gate count and outputs. For a circuit with \(g\) gates, let \(h_2\) count conjunction-form gates whose slots directly read at least two distinct primary-input variables. This is a syntactic count and requires no independence of the values read.

The affine functions of the primary input bits form a submodule of all \(\mathbf F_2\)-valued functions. A Boolean map has independent nonaffine components when every nonzero linear combination of its output coordinates lies outside this submodule. Write \(q\) for the number of conjunction operations in a signed unbounded AND/OR/XOR circuit.

A function \(f:\mathbf F_2^n\to \mathbf F_2\) is affine on an affine flat \(V\) when \(f(x+y+z)=f(x)+f(y)+f(z)\) for all \(x,y,z\in V\); its values off \(V\) are unrestricted, and these functions form a subspace. A map \(F:\mathbf F_2^n\to \mathbf F_2^m\) is nonaffine on flats of \(2^D\) points when no nonzero component \(w\cdot F\) is affine on a flat with at least \(2^D\) points. The least such \(D\) is \(D(F)=A(F)+1\), where \(A(F)\) is the largest dimension of an affine flat on which some nonzero component of \(F\) is affine.

Write \(h=H_2(1/4)\) and \(r=1-H_2(1/8)\). The shared-control coefficient is \(C_{\mathrm s}=(3-h+3r)/(2+2r)\).

A comparator network on \(n\) wires with \(s\) comparators applies its comparators in the order \(0,1,\dots ,s-1\). Comparator \(c\) acts on two distinct wires \(p_c\) and \(q_c\), not necessarily with \(p_c{\lt}q_c\): it puts the smaller of their two values on \(p_c\) and the larger on \(q_c\), and leaves the other wires unchanged. The network acts on values in any linear order, and it commutes with monotone maps. The bottom half \(B\) is the set of wires \(w{\lt}\lfloor n/2\rfloor \) and the top half \(T\) the set of the others. The network is an \(\varepsilon \)-halver when for every input \(x\in \{ 0,1\} ^n\) with \(k\le n/2\) ones, at most \(\varepsilon k\) ones of the output lie in \(B\), and for every input with \(k\le n/2\) zeros, at most \(\varepsilon k\) zeros of the output lie in \(T\). For even \(n\) this is the \(0\)-\(1\) form of the \(\varepsilon \)-halvers of Ajtai, Komlós and Szemerédi (Sorting in \(c\log n\) parallel steps, Combinatorica, 1983): by the commutation with monotone maps, it is equivalent to asking, for every input with distinct values and every \(k\le n/2\), that at most \(\varepsilon k\) of the \(k\) largest inputs end in \(B\) and at most \(\varepsilon k\) of the \(k\) smallest in \(T\).

The wire graph of a comparator network on \(n\) wires with \(s\) comparators is a directed multigraph. Its vertices are an input and an output terminal for every wire and, for every comparator \(c\), its two ends \(c_p\) on \(p_c\) and \(c_q\) on \(q_c\). Its edges are the wire segments, which follow each wire from its input terminal through the ends of the comparators acting on it, in order, to its output terminal, and for every comparator a link from \(c_p\) to \(c_q\).

Write \(\partial S\) for the edges crossing the vertex cut \((S,S^c)\). The helpfulness of flipping a vertex set \(X\) is the signed integer

For \(X\subseteq S\), this is the helpfulness in Monien and Preis’s bisection argument: crossing edges removed minus internal edges made crossing by moving \(X\) to the other side.

A multigraph with distinct vertices \(i_1,\dots ,i_N\) (inputs) and \(o_1,\dots ,o_N\) (outputs), \(2N\) in all, is an \(N\)-hyperconcentrator when for every \(k\), every set of \(k\) inputs is joined to the first \(k\) outputs \(o_1,\dots ,o_k\) by \(k\) vertex-disjoint directed walks. The walks may pass through other inputs and outputs, and every path is a walk, so this includes hyperconcentrators defined with paths. Every superconcentrator is a hyperconcentrator. Parallel edges are counted separately.

Given transcript \(Z\), let the entire left tuple \((X,X_1,\ldots ,X_t)\) be independent of the entire right tuple \((Y,Y_1,\ldots ,Y_t)\). For index sets \(S,T\subseteq [t]\), the actual law applies \(E\) to each source-seed pair and retains \((Z,Y,Y_1,\ldots ,Y_t,(E(X_i,Y_i))_{i\in S\cup T})\) alongside \(E(X,Y)\). It is the deterministic image of the factored source law, and \(S,T\) may overlap.

Let \(D(f)\) and \(L(f)\) be the minimum depth and the minimum number of leaves, constant leaves included, of a De Morgan formula of Theorem 366 computing \(f\); they are defined for every number of inputs, \(0\) included. For \(f\) on \(m\) bits and \(g\) on \(n\) bits, the block composition \(f \diamond g\) applies \(f\) to the values of \(g\) on \(m\) disjoint blocks of \(n\) bits. Substituting formulas gives \(D(f \diamond g) \le D(f) + D(g)\) and \(L(f \diamond g) \le L(f)\, L(g)\) for all \(f\) and \(g\); both bounds are proved.

The Karchmer–Raz–Wigderson conjecture says these bounds are nearly tight. It is formalized in its strong form, with a constant slack. The depth form says that there is a constant \(c\) such that \(D(f) + D(g) \le D(f \diamond g) + c\) for all \(m\), \(n\) and all non-constant \(f\) and \(g\). The size form says that there is a constant \(c\) such that \(L(f)\, L(g) \le c \cdot L(f \diamond g)\) for all such \(f\) and \(g\). The constant does not depend on \(m\), \(n\), \(f\) or \(g\); forms whose slack grows with \(m\) or \(n\) are not formalized. The conjecture is open; it is formalized as a statement only.

Both non-constancy hypotheses are needed. If \(f\) or \(g\) is constant, so is \(f \diamond g\), and it is proved that dropping either hypothesis makes the depth form and the size form false for every \(c\).

From the original law \(w(z)l_z(a)r_z(b)\) compute \(s_1=p(q)\), \(r_1=W(x,s_1)\), \(s_2=Q(q,r_1)\), and \(r_2=W(x,s_2)\), and the same calls on arbitrarily correlated tampered values \(x',q'\). The seed law retains \(z,s_1,s_1',a\) alongside \(s_2\). The output law retains \(z,b,r_1,r_1'\) alongside \(r_2\).

The common transcript records \(Z\), both initial right states, and all four honest and tampered look-ahead outputs. The first refresh applies \(R(y,r_1)\), retaining this transcript and the full left state. The second-output refresh applies \(R(y,r_2)\) and additionally retains \(R(y',r_1')\). Both laws are direct images of the original factored law.

The product \(C=AB\) of two \(n\times n\) matrices over a semiring \(R\) is the map \(R^{n^2+n^2}\to R^{n^2}\) whose output \(C_{ik}\) is \(\sum _jA_{ij}B_{jk}\): the first \(n^2\) inputs hold the entries \(A_{ij}\) of the first factor and the last \(n^2\) inputs the entries \(B_{jk}\) of the second, index pairs numbered row by row. In a circuit computing it, the terminals are the wires of the inputs \(A_{ij}\) and \(B_{jk}\) and the output wires carrying \(C_{ik}\).

Over a commutative semiring \(K\), the outputs of \(n\times n\) matrix multiplication are the polynomials \(C_{ik}=\sum _jA_{ij}B_{jk}\) in the \(2n^2\) inputs. For sets \(c_Y\), \(a_X\), \(b_X\) of index pairs and a set \(H\) of row indices, the row Jacobian sum is

and for a set \(H\) of column indices the column Jacobian sum is its mirror image

For placed terminals \(a\), \(b\), \(c\) (the pairs \((i,j)\), \((j,k)\), \((i,k)\) whose terminals \(A_{ij}\), \(B_{jk}\), \(C_{ik}\) are placed) with heavy rows \(H_I\) and heavy columns \(H_K\), the row Jacobian charge \(L_I\) is the row Jacobian sum of \((c^{\mathsf c},a,b,H_I)\) plus that of \((c,a^{\mathsf c},b^{\mathsf c},H_I^{\mathsf c})\), and the column Jacobian charge \(L_K\) is the column Jacobian sum of \((c^{\mathsf c},a,b,H_K)\) plus that of \((c,a^{\mathsf c},b^{\mathsf c},H_K^{\mathsf c})\).

The terminals of \(n\times n\) matrix multiplication are the edges of the complete tripartite graph on three copies \(I\), \(J\), \(K\) of \(\{ 0,\dots ,n-1\} \): \(A_{ij}\) joins \(i\) and \(j\), \(B_{jk}\) joins \(j\) and \(k\), and \(C_{ik}\) joins \(i\) and \(k\), so every vertex has degree \(2n\). A set of placed terminals (those whose wires lie in a split \(S\)) places \(d(v)\) terminals at each vertex \(v\). The minority at \(v\) is \(g(d(v))=\min \{ d(v),2n-d(v)\} \), and the charges are \(R_I=\sum _{i\in I}g(d(i))\), \(R_J=\sum _{j\in J}g(d(j))\) and \(R_K=\sum _{k\in K}g(d(k))\). A vertex is heavy when \(d(v)\ge n\) and light otherwise.

Set \(d=2^{24}L\) and output width \(2^hL\). On Boolean vectors of source width \(n\) and seed width \(d\), run the scheduled bit program with \(E=e+h+2\) and reserve \(4096(L+E+1)\). Feed exactly its prescribed seed prefix, completed by zero bits when necessary, and read the actual output in flat block order.

A unary runtime parameter \(t\) selects \(h=\lceil \log _2(t+1)\rceil +64\). Test the finite conditions of Theorem 593, then run the actual scheduled program with its exact seed prefix. Invalid parameters return the empty word. The paired interface stores the source and seed words, followed by unary \(t,L,e\).

Test the four finite conditions above before generating the schedule. A valid call cuts the supplied seed word to the exact schedule width and runs the bit program; an invalid call returns the empty word. A paired input supplies the source, seed, and unary depth, scale, and error.

For fixed \(n\) and \(s\), \(\mathsf{MCSP}_{n,s}\) is the Boolean function on \(N = 2^n\) truth-table bits that accepts exactly the truth tables whose (weighted) circuit complexity over a given signature is at most \(s\). Truth tables are indexed big-endian: the first input bit selects the lower or upper half, and pairing two \(2^n\)-bit tables gives the table of the multiplexer on the first bit. This differs from the language \(\mathsf{MCSP}\) of Definition 1107, which uses encoded instances, the library’s AND/OR basis, and little-endian indexing. The main cost model is the imported De Morgan signature with only AND and OR charged.

For \(x\in \mathbf F_2^n\), let \(w_3(x)\in \mathbf F_3\) be its Hamming weight modulo three, interpreting each binary coordinate as zero or one. This is the full three-valued residue, not a Boolean residue predicate.

Two wires of a straight-line program are linked when one is a gate reading the other; the components of the resulting undirected wire graph are its connected components. For a ranking of the wires, the prefix up to a wire \(w\) consists of the wires ranked at most as high as \(w\). For designated output wires and a split \(S\) of the wires with complement \(T\), let \(X_S\) and \(X_T\) be the inputs placed in \(S\) and in \(T\), and \(Y_S\) and \(Y_T\) the outputs whose wires lie in \(S\) and in \(T\). For a function \(f\) and an input \(x\), the left fibre of \(x\) is the set of inputs that agree with \(x\) on \(X_T\) and on which \(f\) agrees with \(f(x)\) on \(Y_T\); the right fibre is defined symmetrically. For a matrix \(M\), \(M[Y, X]\) is its block with rows \(Y\) and columns \(X\).

Apply identity initialization, the specified paired condensers, and the shared one-shot extractor of length \(\ell \) at every leaf. The Boolean interface decodes the entire fixed-length seed word and flattens the \(\mathbf F_2\) outputs in block order.

For depth \(h\), reserve \(Q\), and error exponent \(E\), let

Starting at input width \(N\), recursively use the actual rounded paired condenser width at entropy \(k_i\), rate \(u\), and exponent \(E\). The seed length sums one field seed per level and the final one-shot condenser/hash seed pair. Initialization is the identity and needs no bits.

Encode level seeds in order, followed by the shared final condenser and hash seeds. The workspace records width, remaining depth and its power of two, block count, payload, and unused seed suffix. Each actual condenser step halves the stored remaining power and doubles the count. The final extractor reads both of its seeds at their exact widths.

A constraint network on \(n\) variables is a multigraph whose vertices carry local checks on the bits written on their incident edges, with a port (a vertex and an incident edge) for every variable it reads. It computes \(f\) when the accepted inputs are exactly those admitting an edge assignment that satisfies every check and carries the input on every port. For a prefix \(L\) of a vertex ordering and a cut assignment \(\sigma \), the past set consists of the assignments to the variables read in \(L\) that extend to an edge assignment satisfying the checks of \(L\) and agreeing with \(\sigma \) on the cut; the future set is defined symmetrically. The patterns realized on an edge set \(C\) are the restrictions to \(C\) of satisfying edge assignments. A subset \(T\) determines \(C\) when two satisfying assignments that agree on \(T\) agree on \(C\). The edges charged at a vertex are the cut before it and its incident edges.

Given transcript law \(w(z)\), source kernel \(p_z(a)\), and deterministic message \(f(z,a)\), the new transcript law is \(w'(z,u)=w(z)\Pr [f(z,A)=u\mid z]\). Its updated source kernel is the conditional law of \(A\) on that message, completed uniformly on null rows. Both original source coordinates remain available after updating.

Slice a payload into a runtime number of fixed-width blocks, apply the actual one-shot extractor to every block with the same condenser and hash seed words, and concatenate their \(\ell \)-bit outputs in order. The number of blocks is given in unary; short payloads use the existing total fixed-width slicing convention.

For source length \(n\), output length \(\ell \), and inverse-error exponent \(e\), set \(k=\ell +2e\). Condense with rate parameter \(u=1\) and error exponent \(e+1\). Write \(b\) for its field width and \(N\) for its output width. Choose the hashing field width \(B=2\cdot 3^{s_H}\) by sparse rounding above \(\max (N,\ell )\).

Run the scheduled condenser at \(k=\ell +2e\), error exponent \(e+1\), and \(u=1\), then hash its complete output with an independent field seed. The paired evaluator takes source, both seeds, and unary words for \(n,\ell ,e\). It emits the output bits; the decoded statistical map retains both seeds externally for joint tests.

Apply the concrete eight-call step to both original source pairs with opposite advice bits. Retain the original transcript, both initial and refreshed states, all eight look-ahead outputs, the tampered final output, and the full original left state. The honest final output and this transcript are a direct image of the original factored source law.

For a coefficient \(p\), a slack \(\xi \), and a threshold \(N_0\), the predicate \(\mathrm{PathwidthBound}(p,\xi ,N_0)\) says that every simple \(3\)-regular graph on \(h{\gt}N_0\) vertices has a path decomposition with bags of at most \((p+\xi )h+1\) vertices. The predicate \(\mathrm{CutwidthBound}(c,\xi ,N_0)\) says that every such graph has an injective vertex key all of whose prefixes are crossed by at most \((c+\xi )h\) edges. For a coefficient \(A\), a slack \(\eta \), and a constant \(C\), the graph-ordering hypothesis \(\mathrm{OrderingBound}(A,\eta ,C)\) says that every connected loopless multigraph of maximum degree three with \(N\) vertices and \(M\) edges has a vertex ordering all of whose prefix cuts have at most \((A+\eta )\max \{ M-N,0\} +3\log _2 N+C\) edges.

The parity tests are all nonempty subsets of the coordinate set of size at most \(t\). Given a bad-seed set for each test and each candidate position, the common bad-seed set is their union over both indices.

For a finite weighted sample space and \(m\) coordinates \(\sigma _i\), write \(S=\sum _i\sigma _i\). The parity-bias bound \(\delta \) requires \(|\mathbb E\prod _{i\in T}\sigma _i|\le \delta \) for every nonempty coordinate subset \(T\) of size at most four. The coordinates being signs and the weights being probabilities are separate hypotheses.

A path decomposition ends at \(X\) if it has a last bag and that bag is exactly \(X\); it starts at \(X\) if its first bag is exactly \(X\). Reversal exchanges the endpoint roles. The one-bag decomposition ends at the full vertex set.

Suppress a vertex set \(S\) by retaining vertices outside \(S\), keeping their original edges, and adding an edge between distinct vertices joined by a two-edge path through \(S\). The core graph suppresses the designated region vertices of the region-boundary quotient.

Polynomial multiplication maps the coefficients \(x_0,\dots ,x_{n-1}\) and \(y_0,\dots ,y_{n-1}\) of two polynomials of degree below \(n\), the first and the last \(n\) inputs, to the \(2n-1\) coefficients \(z_m=\sum _{i+j=m}x_iy_j\), \(0\le m\le 2n-2\), of their product; each \(z_m\) is also a polynomial in the \(2n\) inputs. For weights \(\mu \), the Hankel matrix of \(\mu \) is the \(n\times n\) matrix \(\Lambda =(\mu (i+j))\), and \(\left(\begin{smallmatrix} 0 & \Lambda \\ \Lambda ^{\mathsf T} & 0 \end{smallmatrix}\right)\) is indexed by the inputs, the \(x\) first. For a set \(X\) of inputs, \(X\cap x\) and \(X\cap y\) are the coefficients of the two factors whose inputs lie in \(X\).

Fix natural parameters \(a,e\). At input length \(n\), take \(L=\lceil \log _2(n+1)\rceil \), raw depth \(h=a\lceil \log _2(L+1)\rceil \), \(E=e+h+2\), and \(Q=4096(L+E+1)\). Instantiate the specified extractor with leaf length \(L\), source entropy threshold \(k=4^hQ\), and its actual retained seeds. These family definitions do not truncate the depth at small lengths.

For fixed \(a,e\), read a paired source and flat seed word, compute the raw requested depth from the source’s actual length, and call the total scheduled evaluator. Thus one string function covers all source lengths; its clipped runtime behavior is also specified at the exceptional small lengths.

For a supplied polynomial \(E\), set \(g_0=f\bmod E\) and \(g_{j+1}=g_j^2\bmod E\). For exponent \(h=2^r\), output coordinates \(g_{ri}(y)\) for \(0\le i{\lt}m\); the seed \(y\) is kept separate. This is the polynomial map of Guruswami–Umans–Vadhan with the characteristic-power exponent used by Cheraghchi for source linearity. It is an algebraic specification using Mathlib’s polynomial type; an encoded evaluator and uniform field and modulus construction are separate obligations.

A local linear realization assigns a row \(v_w\in F^n\) to every original circuit wire. Input \(j\) carries \(e_j\), and each gate row lies in the span of its argument rows. A polynomial interpretation assigns each operation a polynomial in its argument slots, with unrestricted degree and coefficients. The full polynomial signature contains every such finite-arity polynomial.

A probability weight on a finite type is a nonnegative function \(p\) with \(\sum _xp(x)=1\). Its threshold-\(K\) cap is \(Kp(x)\le 1\) for every \(x\). Statistical distance is \(\frac12\sum _x|p(x)-q(x)|\); deterministic images sum the weights of all preimages. Marginals, uniform weights, and uniform weights supported on a finite subset use the same finite-sum conventions.

The quadratic form of a square matrix \(M\) is \(x\mapsto x^{\mathsf T}Mx\). Over \(\mathbb {Z}/q\), the \(N\times N\) Hankel Cauchy matrix has entries \(1/(i+j+2)\) for \(0\le i,j{\lt}N\).

Starting from an initial seeded map, run \(h\) levels, each using its own fresh seed to condense all current blocks and split their pair outputs. Block alphabets and seed types can vary with the level. Starting from \(t\) blocks, level \(i\) has \(2^it\) blocks. The recursive extractor starts with a single condensed block and finally applies one shared-seed extractor to every leaf. Every seed is retained exactly once.

For depth \(h\), leaf reserve \(Q\), and common error exponent \(E\), set \(k_i=4^{h-i}Q\). Starting from width \(N\), recursively set \(n_{i+1}\) to the actual half-output width of the rate-three condenser on \(n_i\) bits at entropy \(k_i\) and exponent \(E\). Record its actual field seed width \(b_i\). The explicit reserve is \(Q=4096(L+E+1)\).

Let \(B\) be a simple black graph and \(R\) a red multigraph on the same finite vertex set. A set \(X\) is positive if its internal red edges outnumber its external black edges. Red edges retain distinct identities.

A restoration family consists of pairwise disjoint regions \(P_i\) with \(|\partial _B P_i|\le 2\), attached sets \(A_i\) with empty black cut, and a designated red edge between \(P_i\) and \(A_i\). Every \(P_i\) is disjoint from every \(A_j\); the attached sets may overlap one another. Its deleted graph is \(B\) with all cuts \(\partial _B P_i\) removed. Each boundary edge gives one endpoint mark to its endpoint outside \(P_i\). The family’s endpoint marks sum these contributions, retaining multiplicities at a shared outside vertex. These are the data used to restore a supplied family of isolated paths.

Given a joint weighting on an earlier seed and a current state, sample one fresh independent uniform seed, apply the specified deterministic step, and retain the ordered pair of seeds with the output. The new seed is independent of the entire old joint law.

A neighbor map sends each outer seed to a list of base seeds. Coverage \((K,\rho )\) means that every outer support of size at least \(K\) reaches at least a \(\rho \) fraction of base seeds. A somewhere sampler has a candidate list at each outer seed: the small-test failure event occurs when more than a \(2\epsilon \) fraction of outer seeds have every candidate output in the test. It has probability at most \(\delta \) for every source with point masses bounded by \(1/L\).

Supply an \(n\)-bit source and a \(d\)-bit seed to the actual program, where \(d\) is its specified total seed width. Read its output as \(2^h\) successive blocks of \(\ell \) Boolean coordinates. This definition directly runs the bit program and invokes no abstract field enumeration.

Encode the initial field seed, followed by the fresh level seeds in increasing order, followed by the final condenser seed and hash seed. A prefix through any level and the complete tuple are each equivalent to Boolean words of their exact summed field widths. These semantic equivalences require no field-enumeration instances.

Start with the actual rate-one condenser, run the scheduled rate-three paired condensers for \(h\) levels, and apply the actual one-shot extractor with output length \(\ell \) to all leaves. Its seed consists of one initial field seed, one fresh field seed per level, and one final field-seed pair shared by every leaf. Let \(d\) be the sum of their field bit widths.

Run initial compression and every internal level, then consume the final condenser/hash seed pair and extract all leaves. The total wrapper derives the source length from its actual input word and initializes the clipped schedule. Its single paired interface accepts a source, a flat seed word, unary requested depth, and unary error exponent. All projections and component programs are total on malformed encodings.

A runtime state contains the numerical dimensions, block count, concatenated block payload, and unused seed suffix. Initial compression consumes its first seed word. Each later step consumes one fresh seed prefix, applies the actual shared-seed condenser to every block, and keeps its two halves consecutively. The loop executes \(h\) such steps.

Store the current width and entropy in unary, with fixed error exponent \(E\). A numerical step computes the actual rate-three output half-width and divides the entropy by four. For arbitrary requested depth \(r\) and error exponent \(e\), the total initializer selects \(h=\min (r,\lceil \log _2(n+1)\rceil )\), \(E=e+h+2\), the explicit leaf reserve, and the actual rate-one initial compressed width.

Given finitely many seeded maps \(C_i\) and real weights \(w_i\), define the mixture test value as \(\sum _i w_i\Pr [(Y,C_i(X_i,Y))\in T]\). Each \(X_i\) is uniform on its own finite source type, and \(Y\) is an independent uniform seed shared by all components.

Split the wires of a straight-line program, its inputs and its gates, into a set \(S\) and its complement \(\bar S\), and let \(i\) be the number of inputs in \(S\). The forward signals \(A\) are the wires in \(S\) read by some gate in \(\bar S\), and the backward signals \(B\) are the wires in \(\bar S\) read by some gate in \(S\). A signal is the value of one wire, counted once however many gates read it. The boundary key of an input \(x\) is the pair \((a, b)\) of the values of the signals in \(A\) and in \(B\). Mixing \(x\) and \(x'\) takes the coordinates of \(x\) whose input wires lie in \(S\) and the remaining coordinates of \(x'\). For a set \(Z\) of inputs and a key \(\sigma \), the left and right parts \(L_\sigma \) and \(R_\sigma \) are the restrictions of the members of \(Z\) with key \(\sigma \) to the inputs in \(S\) and in \(\bar S\).

Let the original left state determine \(X,X_1,\ldots ,X_t\) and an actual prefix \(Q\). The right state determines its seed family after \((Z,Q)\) is fixed. The source comparison retains \((Z,X_T)\); the seed comparison retains \((Z,Q,Y_S)\). The extraction law is the direct original-law image retaining \((Z,Q)\), complete original right state \(B\), and all actual tampered outputs in \(S\cup T\).