Proof. The assertion is immediate for \(S=\varnothing\), so assume otherwise. Let \((X_{j,a})_{j\in S,\,a\in[k]}\) be independent uniform bits and put \[Z_j=\bigwedge_{a=1}^k X_{j,a}, \qquad F(X)=f(\{j\in S:Z_j=1\}).\] The \(Z_j\) are independent Bernoulli \(p\) bits. Flipping \(X_{j,a}\) changes \(F\) precisely when all the other \(k-1\) bits of its block are one and coordinate \(j\) is pivotal for the values of the other blocks. These two events are independent. Therefore \[ I_{1/2}(F) =k2^{-(k-1)}I_p(f) =2kpI_p(f) \le kb. \tag{2}\] By Theorem 3, there is a Boolean approximant \(H\) to \(F\) with error at most \(\alpha\), using at most \(J_{\mathrm{unif}}(kb,\alpha)\) of the individual bits \(X_{j,a}\). Let \(J\subseteq S\) be the set of blocks touched by these bits. Then \(\lvert J\rvert\le J_{\mathrm{unif}}(kb,\alpha)\).

Reveal all bits in every block indexed by \(J\). Since \(H\) is measurable with respect to these revealed blocks, the Boolean predictor with smallest conditional error from the revealed blocks has total error at most that of \(H\). More explicitly, this predictor outputs one when the conditional probability of \(F=1\) is at least \(1/2\), with any fixed convention at equality. The unrevealed blocks remain independent of the revealed blocks, and the dependence of \(F\) on a revealed block is only through its AND value. Consequently \[\Pr[\,F=1\mid (X_{j,a})_{j\in J,\,a\in[k]}\,] = \Pr[\,f(\{j:Z_j=1\})=1\mid (Z_j)_{j\in J}\,].\] The optimal predictor is therefore a Boolean function only of \((Z_j)_{j\in J}\). Regard it as a function \(\widetilde f:2^S\to\{0,1\}\) on the original coordinates. The induced law of the original input is \(\mu_p^S\), so \[\Pr_{R\sim\mu_p^S}[\,f(R)\ne\widetilde f(R)\,]\le\alpha.\] Thus \(J(p,b,\alpha)=J_{\mathrm{unif}}(kb,\alpha)\) is a valid choice, increased to one if desired. ◻

Proof. For every generating identification in Equation (8), \[(x\circ\operatorname{proj})(\ell(\mathbf s),\ell(w)) =x(\ell(\mathbf s)).\] Thus evaluation is constant on each equivalence class. This remains true when vertices repeat in a tuple: their repeated coordinates are evaluated at the same global label. A rank arc is strictly increasing at every tuple of labels, and hence at the particular tuple supplied by \(\ell\). Its two endpoints cannot become the same equivalence class. Finally, constant profiles all identify with their representatives at the empty tuple, and their evaluated values are the distinct integers \(1,\ldots,N\). ◻

Proof. Fix such a labeling \(\ell\). Delete each wildcard test whose evaluated tuple \(\ell(\mathbf d)\) lies in its star set, and each comparison test whose edge is not satisfied by \(\ell\). Denote this deletion set by \(F_{\mathrm{yes}}\). No rank vertex is deleted.

We first bound its cost. In a full-prefix test, conditional on any fixed vertex tuple \(\mathbf s\), the count \[\#\{j:i_j=i,\ \ell(u_j)\in P_j\}\] is binomial with mean \(\mu_i=p_iT/M\). Indeed, indices and subsets are independent between slots, so every slot contributes an independent Bernoulli variable of parameter \(p_i/M\). This argument also applies when the same game vertex appears in several slots. For a binomial random variable \(Z\) of mean \(\mu\), the exponential Markov inequality gives \[\Pr[Z<\mu/2] \le e^{\mu/2}\mathbb E[e^{-Z}] \le\exp\bigl(-(1/2-e^{-1})\mu\bigr) \le\exp(-\mu/8).\] Here the middle inequality follows by writing \(\mathbb E[e^{-Z}]=(1-a+ae^{-1})^T\le\exp(-Ta(1-e^{-1}))\) when \(Z\) has parameters \(T,a\). Applying this bound to each scale and taking a union bound over \(i\in[M]\), the deletion probability for a full-prefix test is at most \[\sum_{i=1}^{M}\exp(-\mu_i/8) \le M\exp\left(-\frac{p_MT}{8M}\right).\] After multiplication by the mass \(H\), this is at most one by Equation (3). In a single-label test, membership of the evaluated tuple in the star set is precisely the event \(j_0=\ell(w)\). Its probability is \(1/m_w\), so each of the two families contributes cost one. Comparison tests are deleted with probability at most \(\theta\), and hence contribute at most \(K\theta\le1\) by Equation (5). Thus \[w(F_{\mathrm{yes}})\le 1+1+1+1=4.\]

To prove that this deletion set is a feedback vertex set, assign to each rank vertex its evaluation under \(\ell\), as in Lemma 7. Every rank arc strictly increases the assigned value. For a retained wildcard vertex, let \(C_r\) be the cell containing its evaluated tuple and assign the test value \(z_r\). The evaluated tuple is outside the star set. Thus Equations (9) and (10), at that tuple, put every incoming rank value strictly below \(z_r\) and every outgoing rank value strictly above it.

For a retained comparison, the evaluated prefix is the same on both sides and \(\pi_e(\ell(u))=\ell(v)\). By Equation (13), \[\ell(\mathbf s u)\in E_u^r(R_u) \quad\Longrightarrow\quad \ell(\mathbf s v)\in E_v^r(R_v).\] The possible pairs of rank indices at the start and end of Equation (15) are therefore \((2,3)\), \((2,18)\), and \((17,18)\). Each is increasing, so the corresponding evaluated values are strictly increasing as well. Assign this test any real value strictly between its two endpoint values.

These assignments coexist because there are no arcs between test vertices. Every arc remaining after deletion of \(F_{\mathrm{yes}}\) strictly increases the assigned real value. A directed cycle would force a strict increase back to its starting value, which is impossible. Thus the remaining digraph is acyclic. ◻

Proof. Put \(n=1+\lvert U\rvert+\lvert V\rvert+\lvert E\rvert\), counting parallel constraints as distinct edges if necessary. The number of allowed tuples is at most \((2T+1)n^T\). By Equation (7), a tuple has at most \(N^{m^T}\) formal rank vertices. Both factors other than \(n^T\) are constants for fixed \(A\).

For each slot, there are at most \(M2^m\) choices of index and subset. The support of the rank law, the number of permutations of either alphabet, and all choices of individual labels are also bounded by constants. A full-prefix test uses \(T\) game-vertex slots, so this family has \(O_A(n^T)\) outcomes. A single-label test has at most \(T-1\) prefix vertices and one endpoint, again giving \(O_A(n^T)\) outcomes. A comparison test has at most \(T-1\) prefix vertices and one input edge; its remaining choices, including the coupled subsets and candidate cell, range over constant finite sets. Thus there are \(O_A(n^T)\) comparison outcomes as well. Here \(O_A\) allows the implicit constant to depend on \(A\).

Within a tuple there are at most \(N^{2m^T}\) formal rank arcs, and a wildcard vertex has at most \(2N^{m^T}\) incident arcs. Comparisons have two arcs each. Therefore the total numbers of formal vertices and arcs are \(O_A(n^T)\). Computing the equivalence relation in Equation (8) and discarding duplicate arcs cannot increase these counts. Lemma 7 rules out rank self-loops, and every other arc joins a rank vertex to a distinct test vertex.

It remains to account for numerical representation. Marginal endpoint probabilities are sums of input rational edge probabilities. They can be computed with polynomial bit length: a common denominator can be formed from the product of the input denominators, whose bit length is at most their total encoding length. Every outcome probability is a product of at most \(T+1\) input-dependent edge or endpoint probabilities and a fixed number of rational factors depending only on \(A\). Its bit length is therefore polynomial in the input encoding length. Zero-probability outcomes are omitted. The rank law supplied by Lemma 13 is a fixed finite rational table and may be hardwired into the reduction for this fixed \(A\). Alternatively, a computable finite Ramsey bound and exhaustive search over finite rational probability tables recover such a law: each total-variation constraint is an exact rational inequality, and the strict slack in the proof of Lemma 13 ensures that the search terminates. This preprocessing depends only on \(A\), not on the input game.

Finally, each outcome probability is at most one. Every test cost is therefore at most its family’s total mass, while every rank cost is \(D+1\). All costs are bounded by \[C_A=\max\{D+1,H,m,\lvert Y\rvert,K\},\] which depends only on \(A\). These estimates establish both the claimed running time and the cost bound. No efficient dependence on a variable parameter \(A\) is asserted. ◻

Proof. Choose a positive number \(\delta<\eta/2\). Let \(\mathcal I=\binom{[L]}{3}\). Partition \([0,1]\) into a finite number \(b\) of intervals, each of diameter at most \(\delta\), assigning boundary points to one of their adjacent intervals. The finite Ramsey theorem for triples (Ramsey 1930, Theorem B) gives an \(N\) such that every coloring of \(\binom{[N]}{3}\) with at most \(b^{\lvert\mathcal I\rvert^2}\) colors has a monochromatic set of size \(L\).

Consider the following finite zero-sum game. The minimizing player chooses an increasing map \(\psi\colon[L]\hookrightarrow[N]\). The maximizing player chooses a triple \((I,I',\mathcal A)\), where \(I,I'\in\mathcal I\) and \(\mathcal A\subseteq\binom{[N]}{3}\). The payoff to the maximizing player is \[\mathbf 1\{\psi(I)\in\mathcal A\}-\mathbf 1\{\psi(I')\in\mathcal A\}.\] Fix an arbitrary mixed strategy \(\tau\) of the maximizing player. Let \(w_{I,I'}\) be its marginal probability of the ordered pair \((I,I')\). When \(w_{I,I'}>0\), define, for \(Z\in\binom{[N]}{3}\), \[q_{I,I'}(Z)=\Pr_{\tau}[Z\in\mathcal A\mid I,I'];\] put \(q_{I,I'}(Z)=0\) when \(w_{I,I'}=0\). Color \(Z\) by the vector of intervals containing \(q_{I,I'}(Z)\), one interval for every ordered pair \((I,I')\in\mathcal I^2\). The number of possible colors is at most \(b^{\lvert\mathcal I\rvert^2}\), so there is a monochromatic \(L\)-element set. Let \(\psi\) be its increasing enumeration. For every ordered pair \((I,I')\), both \(\psi(I)\) and \(\psi(I')\) are triples in this set, and hence \[\lvert q_{I,I'}(\psi(I))-q_{I,I'}(\psi(I'))\rvert\le\delta.\] The expected payoff against \(\tau\) is consequently at most \[\sum_{I,I'\in\mathcal I}w_{I,I'}\, \bigl(q_{I,I'}(\psi(I))-q_{I,I'}(\psi(I'))\bigr) \le\delta.\] The number \(N\) was chosen from a bound on the number of colors that does not depend on \(\tau\). Thus every mixed strategy of the maximizing player has a pure response with payoff at most \(\delta\).

By the finite minimax theorem (Neumann 1928, sec. II.3), there is a probability distribution \(\mu\) on increasing maps for which the expected payoff against every pure test is at most \(\delta\). Choose a rational probability distribution \(\widehat\mu\) on the same finite space with \[\sum_{\psi}\lvert\widehat\mu(\psi)-\mu(\psi)\rvert<\eta/2.\] Such distributions are dense in the finite probability simplex. Since each payoff lies in \([-1,1]\), this replacement changes any expected payoff by less than \(\eta/2\). Thus every pure test has expected payoff less than \(\delta+\eta/2<\eta\) under \(\widehat\mu\). The ordered pairs include both \((I,I')\) and \((I',I)\), and \(\mathcal A\) ranges over all subsets of \(\binom{[N]}{3}\). The resulting inequalities give Equation (16). ◻

Proof. Fix \(\mathbf d\) and \(E\subseteq\Lambda_{\mathbf d}\). For integers \(r_1<r_2<r_3\) in \([N]\), let \(x_{r_1,r_3}\) be the profile taking value \(r_1\) on \(E\) and \(r_3\) on its complement. Once the surviving order is fixed, the function \[(r_1,r_2,r_3)\longmapsto \mathbf 1\{b_{\mathbf d}(x_{r_1,r_3})\prec o_{r_2}\}\] is a deterministic Boolean function of this triple alone. Applying Lemma 13 to it shows that \[ \lvert\mathbb E_{\psi}G_{\mathbf d}(E;a,c,h) -\mathbb E_{\psi}G_{\mathbf d}(E;a',c',h')\rvert\le\eta \tag{20}\] for any two increasing triples of positions, whether usable or not.

Equation (20) compares expectations; it does not by itself control disagreement under the same embedding. We obtain that control through pointwise ordered pairs of bits, for which the probability of disagreement equals the absolute difference of expectations. Fix a usable triple \((a,c,h)\) and abbreviate \[\begin{split} A_0&=G_{\mathbf d}(E;2,15,L-1),\\ A_1&=G_{\mathbf d}(E;2,c,L-1),\\ A_2&=G_{\mathbf d}(E;1,c,c+1),\\ A_3&=G_{\mathbf d}(E;a,c,h). \end{split}\] The bits \(A_0\) and \(A_1\) compare the same rank vertex to two constant vertices. They are pointwise ordered: \(A_0\le A_1\) if \(c\ge15\), and \(A_1\le A_0\) if \(c\le15\). Equation (20) therefore gives \(\Pr[A_0\ne A_1]\le\eta\).

The profile of \(b_{\mathbf d}^{\psi}(E;1,c+1)\) is strictly smaller at every coordinate than the profile of \(b_{\mathbf d}^{\psi}(E;2,L-1)\): on \(E\) use \(1<2\), and on its complement use \(c+1<L-1\). The strict rank arc from the former vertex to the latter forces \(A_2\ge A_1\). Similarly, \(1<a\) and \(c+1<h\) imply \(A_2\ge A_3\). Applying Equation (20) to these ordered pairs gives \[\Pr[A_1\ne A_2]\le\eta, \qquad \Pr[A_2\ne A_3]\le\eta.\] A union bound yields \[\Pr\bigl[G_{\mathbf d}(E;a,c,h)\ne g_{\mathbf d}(E)\bigr] \le3\eta.\] There are at most \(L^3\) usable triples and \(2^{\lvert\Lambda_{\mathbf d}\rvert}\) subsets \(E\). A second union bound proves the first inequality of Equation (19). Every allowed tuple has length at most \(T\) and each slot alphabet has size at most \(m\), so \(\lvert\Lambda_{\mathbf d}\rvert\le m^T\). The choice \(3\eta L^3 2^{m^T}\le\rho\) proves the second inequality. Finally, averaging the pointwise bound over any tuple distribution independent of \(\psi\) gives the last assertion. ◻

Proof. For \(E\subseteq E'\), compare \[b_{\mathbf d}^{\psi}(E';2,17) \quad\text{and}\quad b_{\mathbf d}^{\psi}(E;3,18).\] The first profile is strictly smaller everywhere: the index pairs in \(E\), \(E'\setminus E\), and \(\Lambda_{\mathbf d}\setminus E'\) are, respectively, \((2,3)\), \((2,18)\), and \((17,18)\). The rank arc consequently implies \[G_{\mathbf d}(E';2,15,17) \ge G_{\mathbf d}(E;3,15,18).\] Both triples are usable, so goodness identifies these two bits with \(g_{\mathbf d}(E')\) and \(g_{\mathbf d}(E)\). For the extreme sets, the reference profile is \(o_{\psi(L-1)}\) when \(E=\varnothing\) and \(o_{\psi(2)}\) when \(E=\Lambda_{\mathbf d}\). Their positions relative to \(o_{\psi(15)}\) give the claimed values. ◻

Proof. The profile on \(\Lambda_{\mathbf s w}\) that takes value \(\psi(a)\) on \(E\times\Lambda_w\) and \(\psi(h)\) elsewhere is the pullback of the corresponding profile on \(\Lambda_{\mathbf s}\) under the projection dropping the last slot. Definition 6 identifies the two rank vertices. Their comparisons to the same constant marker are identical, proving Equation (21). Apply this identity both to the reference triple and to every usable triple: goodness of the extension gives goodness of the shorter tuple for each subset \(E\). Iteration proves the final assertion. The projection identity holds on the formal product alphabets even when a game vertex occurs in more than one slot. ◻

Proof. Set \(c=10d+15\) and define the rank vertices \[v^-=b_{\mathbf d}^{\psi}(E;2,c+2), \qquad v^+=b_{\mathbf d}^{\psi}(E\cup Z;c-2,L-1).\] We first check the wildcard’s incident arcs. If \(\lambda\in C_\ell\setminus Z\) with \(\ell\le d\), then \(\lambda\in E\), so the two profiles take values \(\psi(2)\) and \(\psi(c-2)\), respectively. The inequalities \[2<10\ell+10\le10d+10<c-2\] place these values strictly below and strictly above \(z_\ell=\psi(10\ell+10)\). If instead \(\ell>d\), then \(\lambda\notin E\cup Z\), so the profiles take values \(\psi(c+2)\) and \(\psi(L-1)\). Here \[c+2=10d+17<10\ell+10 \le10k_{\max}+10=L-20<L-1,\] which gives the required strict inequalities again. Thus the constructed digraph contains the arcs \[v^-\longrightarrow v_{\mathrm{test}}\longrightarrow v^+.\] Empty cells impose no conditions in these checks. The first case is absent when \(d=0\), and the second is absent when \(d=k\).

Since \(0\le d\le k\le k_{\max}\) and \(L=10k_{\max}+30\), \[15\le c\le L-15.\] Both \((2,c,c+2)\) and \((c-2,c,L-1)\) are therefore usable triples. Goodness and Equation (22) show that \(v^-\) does not precede \(o_{\psi(c)}\), whereas \(v^+\) does precede it. If \(v_{\mathrm{test}}\) survived, the displayed path would give \(v^-\prec v_{\mathrm{test}}\prec v^+\prec o_{\psi(c)}\), a contradiction. Hence \(v_{\mathrm{test}}\in F\). ◻

Proof. Let \(\mathcal G\) be the event that both extended tuples \(\mathbf s u\) and \(\mathbf s v\) are good. The tuple choices are independent of \(\psi\), so Lemma 15, averaged over these choices, gives \(\Pr[\mathcal G^c]\le2\rho\). On \(\mathcal G\), both conditioned functions use the same prefix transition index \(r_*\), by Definition 19 and Lemma 17.

Suppose that \(\mathcal G\) holds and that \(f_u(R_u)=1,\ f_v(R_v)=0\). Add the candidate-cell draw from the comparison test and consider the outcome \(r=r_*\). The start and end rank vertices of Equation (15) are then \[b_{\mathbf s v}^{\psi} (E_v^{r_*}(R_v);2,17), \qquad b_{\mathbf s u}^{\psi} (E_u^{r_*}(R_u);3,18).\] The triples \((2,15,17)\) and \((3,15,18)\) are usable. Goodness and the two function values show that the start does not precede \(o_{\psi(15)}\), whereas the end precedes \(o_{\psi(15)}\). If the test vertex were retained, its two arcs would require the start to precede the test vertex and the test vertex to precede the end. This contradicts the fixed topological order. Hence that comparison vertex belongs to \(F\).

For fixed \((\mathcal D,e,R_u,R_v)\) as above, the candidate-cell draw hits \(r_*\) with probability \(2^{-t}\ge2^{-T}\). Let \(\delta_i\) be the probability that a comparison vertex is deleted when its fresh threshold index is fixed to \(i\), including the candidate-cell draw. We have proved \[\delta_i\ge 2^{-T}\Pr_{\mathrm c,i} [\,\mathcal G,\ f_u(R_u)=1,\ f_v(R_v)=0\,].\] In the actual comparison family the threshold index is uniform on \([M]\). Its deleted weight is \[\frac K M\sum_{j=1}^{M}\delta_j\le D,\] so \(\delta_i\le MD/K\). Combining these inequalities and then adding \(\Pr[\mathcal G^c]\le2\rho\) proves Equation (31). ◻

Proof. Independently for each vertex with a nonempty list, choose its label uniformly from that list. Give every empty-list vertex any fixed label from its alphabet. If \(\pi_e(J_u)\cap J_v\ne\varnothing\), there is at least one pair \((x,y)\in J_u\times J_v\) with \(\pi_e(x)=y\). Since \(u\) and \(v\) are different vertices, the probability of choosing that pair is \[\frac1{\lvert J_u\rvert\lvert J_v\rvert}\ge\frac1{J^2}.\] The expected value of this random labeling is therefore at least the displayed intersection probability divided by \(J^2\). Every deterministic labeling in its support has value at most \(\theta\), so the expected value is at most \(\theta\). This proves the claim. For the conditional assertion, fix the conditioning data first and repeat the same argument; independence leaves the fresh edge law equal to \(\nu\). ◻

Proof. Fix \(i\). For each value of \(\mathcal D\), construct a junta approximant for each game vertex, before drawing the fresh edge. For notation, put \[\beta_{w,i}= \begin{cases} p_i,&w\in U,\\ q_i,&w\in V. \end{cases}\] If \(B_w\le B_0\), Lemma 23 gives \(I_{\beta_{w,i}}(f_w)\le B_0\). Corollary 4 and the choice of \(J\) in Section 3.1 therefore provide a Boolean function \(\widetilde f_{w,i}\) on a coordinate set \(J_w\subseteq\Lambda_w\), with \[ \lvert J_w\rvert\le J,\qquad \Pr_{R\sim\mu_{\beta_{w,i}}^{\Lambda_w}} [\,f_w(R)\ne\widetilde f_{w,i}(R)\,]\le\gamma. \tag{33}\] Choose one such pair by a fixed ordering of the finitely many possible coordinate sets and Boolean truth tables. If \(B_w>B_0\), set \(J_w=\varnothing\) and choose \(\widetilde f_{w,i}\) to be the constant-zero function; no error guarantee is asserted at that vertex. We suppress the dependence of \(J_w\) on \(\mathcal D\) and \(i\).

This defines one list for every actual game vertex from \((\mathcal D,i)\) alone. The functions \(f_w\), including the fallback functions, are already defined for all vertices from \(\mathcal D\) alone. Thus the choice of a junta or list uses no information about the fresh sampled edge. It may depend on the fixed game instance and the fixed topological order, as may any labeling used in a soundness argument. A repetition in the prefix, or an endpoint that also occurs in the prefix, does not change this conditional independence: the fresh edge was drawn independently of the entire prefix.

By Lemma 26, for every fixed value of \(\mathcal D\), \[\Pr_{e\sim\nu} [\,\pi_e(J_u)\cap J_v\ne\varnothing \mid\mathcal D\,]\le\theta J^2.\] After averaging over \(\mathcal D\), this remains the bound on the list-intersection event under the common law. Also, Proposition 24 and Markov’s inequality give the averaged bound \[ \Pr[\,B_u>B_0\ \text{or}\ B_v>B_0\,] \le\frac{\mathbb EB_u+\mathbb EB_v}{B_0} \le 2\gamma. \tag{34}\] Here we have used the actual endpoint marginals of \(\nu\). Equation (34) is a bound under the joint law of \((\mathcal D,e)\); no corresponding pointwise bound conditional on \(\mathcal D\) is needed.

Let \(\mathcal A_i\) be the event, determined by \((\mathcal D,e)\), that both budgets are at most \(B_0\) and \(\pi_e(J_u)\cap J_v=\varnothing\). The preceding bounds imply \[ \Pr[\mathcal A_i^c]\le2\gamma+\theta J^2. \tag{35}\] Fix \((\mathcal D,e)\) in \(\mathcal A_i\). In the coupled experiment, all bits used by the big-side junta belong to fibers indexed by \(\pi_e(J_u)\), and all bits used by the small-side junta belong to fibers indexed by \(J_v\). These are disjoint collections of independently generated fibers. Consequently \(\widetilde f_{u,i}(R_u)\) and \(\widetilde f_{v,i}(R_v)\) are independent in the coupled experiment. They are also independent in the independent experiment, and their marginal distributions are unchanged. Their joint distributions therefore agree in the two experiments. This includes the case of a constant junta with an empty coordinate set.

The conditional approximation error for each endpoint in Equation (33) is at most \(\gamma\) in either experiment, because both have exactly the stipulated product marginals. Replacing \(f_u,f_v\) by their respective juntas changes the conditional probability of the pattern \((1,0)\) by at most \(2\gamma\), by a union bound. Doing this in both experiments and using equality of the junta joint distributions yields \[\begin{align*} &\left| \Pr_{\mathrm{ind},i}[\,f_u(R_u)=1,\ f_v(R_v)=0 \mid\mathcal D,e\,] \right.\\[-2mm] &\hspace{22mm}\left. -\Pr_{\mathrm c,i}[\,f_u(R_u)=1,\ f_v(R_v)=0 \mid\mathcal D,e\,] \right|\le4\gamma \end{align*}\] on \(\mathcal A_i\). On its complement the difference is at most one. Integrating over the unchanged law of \((\mathcal D,e)\), and using Equation (35) and Lemma 25, gives \[\begin{align*} &\Pr_{\mathrm{ind},i}[\,f_u(R_u)=1,\ f_v(R_v)=0\,]\\ &\qquad\le 2\rho+\frac{M2^T D}{K} +2\gamma+\theta J^2+4\gamma \le10\gamma. \tag{36}\end{align*}\] The conditional probability of the pattern in the independent experiment is exactly \(h_u(p_i)(1-h_v(q_i))\). Finally, \(\gamma=p_M/1000\) and \(p_M\le p_i\), so \[10\gamma=\frac{p_M}{100}\le\frac{p_i}{16}.\] This proves Equation (32). ◻

Proof. Suppose that \(F\) has cost at most \(D\), as assumed throughout this section. Fix \(i\in[M]\), and let \[\mathcal H_i=\{h_v(q_i)\ge1/2\}\] under the common distribution of \((\mathcal D,e)\). On its complement, \(h_u(p_i)\le2h_u(p_i)(1-h_v(q_i))\). Consequently Propositions 21 and 27 imply \[\begin{align*} \mathbb E[\,h_u(p_i)\mathbf 1\{\mathcal H_i\}\,] &=\mathbb Eh_u(p_i) -\mathbb E[\,h_u(p_i)\mathbf 1\{\mathcal H_i^c\}\,]\\ &\ge\frac{p_i}{4} -2\mathbb E[\,h_u(p_i)(1-h_v(q_i))\,]\\ &\ge\frac{p_i}{8}. \end{align*}\] Since \(0\le h_u(p_i)\le1\), we obtain \(\Pr[\mathcal H_i]\ge p_i/8\). Lemma 23 also gives \(h_v(q_i)\le q_iB_v=2p_iB_v\) pointwise. Thus, on \(\mathcal H_i\), one has \(B_v\ge1/(4p_i)\), and hence \[ \Pr\!\left[B_v\ge\frac1{4p_i}\right]\ge\frac{p_i}{8}, \qquad i\in[M]. \tag{37}\]

These are tail estimates for one random variable \(B_v\) under one fixed probability law. The definition of \(f_v\), and therefore that of \(B_v\), does not use the fresh threshold index \(i\). The junta approximants used to prove the individual estimates may depend on \(i\), but this does not alter \(B_v\).

Put \(a_i=1/(4p_i)\) for \(i\ge1\), and \(a_0=0\). For every real \(x\ge0\), \[x\ge\sum_{i=1}^{M}(a_i-a_{i-1})\mathbf 1\{x\ge a_i\}.\] Indeed, if \(a_j\) is the largest crossed threshold, the sum on the right telescopes to \(a_j\le x\); if no threshold is crossed, it is zero. Taking expectations and using Equation (37) yields \[\mathbb EB_v \ge\sum_{i=1}^{M}(a_i-a_{i-1})\Pr[B_v\ge a_i] \ge\sum_{i=1}^{M}\frac{a_i}{2}\frac{p_i}{8} =\frac M{64}.\] Here \(a_i=2a_{i-1}\) for \(i\ge2\), while \(a_1-a_0=a_1\ge a_1/2\). Since \(M=128(D+1)\), this gives \(\mathbb EB_v\ge2(D+1)\), contradicting Proposition 24. No feedback vertex set of cost at most \(D\) can therefore exist. ◻