9 Derandomization
The algorithms of Theorems 3.5 and 4.1 are randomized. Classical Monotone Local Search is derandomized by (Fomin et al. 2019) at the price of a factor \(2^{o(n)}\) in the running time. For sample-dependent running-time exponents the answer has two parts. If the algorithm may use the running-time exponent and the extension algorithm only as oracles, no deterministic algorithm matches the mean-exponent theorem in general: when the mean bound, at least \(1\), is below \(\log\binom kt\) by a linear amount, where \(t\) is the sample size, its cost exceeds that of the randomized algorithm by an exponential factor unless it reaches the cost \(\binom nk\) of testing every \(k\)-set (Theorems D.6.1 and D.6.3 and Corollary D.6.2), and for the exponential-moment theorem the lower bound can come close to \(\binom nk\) (Theorem 9.4); for the mean bounds of Connected Dominating Set the gap is \(1.7547^n/\operatorname{poly}(n)\) against \(\sqrt3^{\,n}\operatorname{poly}(n)\) (Corollary 9.3). If, however, the mean bound comes from a pointwise affine majorant \(g(X)\le\alpha-w(X)\), where \(g(X)=g(I,X,k)\) is the shorthand declared after Definition 3.2 and \(w\) are unknown nonnegative weights of known total, then balanced set-inclusion families, which we list deterministically in polynomial space (Theorem 9.6), derandomize, for integer weights and with a factor \(2^{O(n(\log\log n)^{2}/\log n)}\), the exponential-moment bound of the affine surrogate exponent \(\alpha-w(X)\) (Theorem 9.10). This is not a derandomization of Theorem 3.5 for the true running-time exponent \(g\). Section 10 derives the consequences for Connected Dominating Set.
Throughout we use the setting of Definitions 3.1, 3.2 and 3.3. An implicit set system \(\Phi\) assigns to an instance \(I\) with \(N=|I|\) a universe \(U_I\) with \(n=|U_I|\le N\) and a family \(\mathcal{F}_I\) of solutions; an extension algorithm \(\mathcal{A}\) decides, given \((I,X,k)\), whether some \(Y\subseteq U_I\setminus X\) with \(|Y|\le k-|X|\) has \(X\cup Y\in\mathcal{F}_I\), in time \(2^{g(I,X,k)}N^{O(1)}\), where the running-time exponent \(g\ge0\) is computable in polynomial time. For a solution \(S\) with \(|S|=k\) we write \(\mu_t(S)=\sum_{X\in\binom St}2^{-g(I,X,k)}\), and \(H\) is the binary entropy, with the estimates (1).
9.1 Set-inclusion families and what changes with sample-dependent running times
Classical Monotone Local Search samples a uniform \(t\)-subset \(X\) of the universe and calls the extension algorithm on it. The running-time bound \(c^{k-t}N^{O(1)}\) of the extension call depends only on \(|X|\), so a sample \(X\) of size \(t\) can fail only by not being contained in the solution. (Fomin et al. 2019) replace the random samples by a deterministic family that contains a \(t\)-subset of every \(k\)-set.
Definition 9.1 (Set-inclusion family (Fomin et al. 2019)). Let \(|U|=n\) and \(0\le t\le k\le n\). A family \(\mathcal J\subseteq\binom Ut\) is an \((n,k,t)\)-set-inclusion family if every \(S\in\binom Uk\) contains some member of \(\mathcal J\).
Every member of \(\binom Ut\) lies in \(\binom{n-t}{k-t}\) sets of \(\binom Uk\), so double counting gives \(|\mathcal J|\ge\binom nk/\binom{n-t}{k-t}=\binom nt/\binom kt\). (Fomin et al. 2019, sec. 3) construct families of size \(\binom nt\binom kt^{-1}2^{o(n)}\) in time of the same order: they hash the universe into about \(\log n\) buckets with a pairwise independent family of functions, build a near-optimal family on each bucket by greedy Set Cover, and combine the bucket families. The bucket families have size \(2^{O(n/\log n)}\) and are stored, and the paper notes that the deterministic algorithm needs an additional \(2^{o(n)}\) space. Looping over such a family instead of sampling gives a deterministic \((2-\frac1c)^{n+o(n)}N^{O(1)}\) algorithm from a \(c^{k}N^{O(1)}\) extension algorithm.
A sample-dependent running-time exponent changes the picture. The family must now contain, inside every solution, a sample of small running-time exponent, and the running-time exponents of the subsets of the solution are visible only through evaluations of \(g\). An adversary can give large running-time exponents to exactly the evaluated subsets; this planting argument gives the lower bounds of Section 9.2. For running-time exponents bounded by an affine function of unknown nonnegative weights, a family with a stronger property suffices (Section 9.3): it contains, inside every solution, a sample of at least average weight. This balance is strictly stronger than inclusion: \(\{\{1\},\{2\},\{3\}\}\) is a \((4,2,1)\)-set-inclusion family, but for \(S=\{1,4\}\) and a weight concentrated on the element \(4\), no member inside \(S\) has positive weight.
9.2 The black-box barrier
The randomized algorithms of Theorems 3.5 and 4.1 use the instance only through evaluations of \(g\) and calls of \(\mathcal{A}\). The barrier concerns deterministic algorithms with the same access, and with membership tests added.
Definition 9.2 (Black-box model). An instance is a pair \((\mathcal{F},g)\) with \(\mathcal{F}\subseteq2^{U}\), \(|U|=n\), and \(g\colon2^{U}\times\mathbb{N}\to\mathbb{R}_{\ge0}\). The algorithm knows \(n\), \(k\) and the parameters of the hypothesis (\(t\) and \(\lambda\), \(\lambda_0,\dots,\lambda_k\), or \(\psi\) and \(\Gamma\), below). It may call
\(\mathrm{COST}(X,\ell)\), for a set \(X\subseteq U\) and an integer \(\ell\ge0\), which returns \(g(X,\ell)\), at cost \(1\);
\(\mathrm{EXT}(X,\ell)\), which returns whether some \(Y\subseteq U\setminus X\) with \(|Y|\le\ell-|X|\) has \(X\cup Y\in\mathcal{F}\), at cost \(2^{g(X,\ell)}\);
\(\mathrm{MEM}(X)\), which returns whether \(X\in\mathcal{F}\), at cost \(1\).
Computation is free. A deterministic algorithm is correct for a class \(\mathcal{C}\) of instances if it answers no if \(\mathcal{F}\) contains no set of size at most \(k\), and it answers yes on every instance of \(\mathcal{C}\) in which \(\mathcal{F}\) contains a set of size exactly \(k\). Its cost on an instance is the total cost of its calls. With \(\mathbb{E}_{X\in\binom St}\) the mean over \(X\in\binom St\), the classes are:
\(\mathcal{C}_{\mathrm{mean}}(t,\lambda)\): every \(S\in\mathcal{F}\) with \(|S|=k\) satisfies \(\mathbb{E}_{X\in\binom St}g(X,k)\le\lambda\);
\(\mathcal{C}_{\mathrm{mean}}^{\mathrm{all}}(\lambda_0,\dots,\lambda_k)\): every \(S\in\mathcal{F}\) with \(|S|=k\) satisfies \(\mathbb{E}_{X\in\binom Sj}g(X,k)\le\lambda_j\) for every \(j\in\{0,\dots,k\}\);
\(\mathcal{C}_{\mathrm{exp}}(\psi,\Gamma)\): some \(S\in\mathcal{F}\) with \(|S|=k\) has \(\max_j\mu_j(S)/\binom nj\ge2^{-\psi n}/\Gamma\), where \(\mu_j(S)=\sum_{X\in\binom Sj}2^{-g(X,k)}\).
The model is generous to the algorithm: computation is free, every evaluation of \(g\) costs one step, and \(\mathcal{F}\) need not be monotone. The randomized algorithms of Theorem 4.1 (on \(\mathcal{C}_{\mathrm{mean}}(t,\lambda)\)) and Theorem 3.5 (on \(\mathcal{C}_{\mathrm{exp}}(\psi,\Gamma)\)) run in this model within their stated bounds, since they only evaluate \(g\) and call the extension algorithm. Write \[\mathsf R_t=\binom nt\binom kt^{-1}2^{\lambda}\] for the running-time bound of the mean-exponent theorem at sample size \(t\), without its polynomial factor; Theorem 4.1 decides the class \(\mathcal{C}_{\mathrm{mean}}(t,\lambda)\) with one-sided error in time \(\mathsf R_t\) up to a factor polynomial in \(N\) and \(\lambda\) (the Markov-cutoff algorithm of Remark 4.2, with the exact threshold \(\lambda+1\), runs \(\lceil(\lambda+1)\binom nt\binom kt^{-1}\rceil\) trials of cost at most \(1+2^{\lambda+1}\) each, a total cost of at most \(6(\lambda+1)\mathsf R_t\)).
The idea.
All lower bounds use one adversary, a form of the planting argument of the oracle lower bounds of (Esmer et al. 2022, 2024), where a solution is hidden among the sets that a run leaves unqueried. It runs a deterministic algorithm on a no-instance, \(\mathcal{F}=\emptyset\), whose running-time exponents depend only on the size of the sample. Call a set touched if the run evaluates its running-time exponent or calls the extension algorithm on it, and call a \(k\)-set clean if the run neither tests its membership nor calls the extension algorithm on one of its subsets. A clean \(k\)-set can be planted as the only solution, with running-time exponent \(0\) on its untouched subsets, without changing any answer of the run, so the algorithm still answers no. A cheap run leaves a random \(k\)-set clean with few touched subsets, and then the planted instance satisfies the hypothesis of the class, which contradicts correctness. The proofs are in Appendix D.6.
Mean exponents.
The planting argument gives lower bounds for the hypothesis of Theorem 4.1 at one sample size and for mean bounds \(\lambda_0,\dots,\lambda_k\) at all sample sizes; in both cases a deterministic black-box algorithm has cost about \(\binom nt\) instead of \(\mathsf R_t\), up to the cap \(\binom nk\) of testing every \(k\)-set, so the gap to the randomized algorithm is exponential whenever \(\log\binom kt\) exceeds the mean bound by a linear amount. The statements are in Appendix D.6.1 (Theorem D.6.1, Corollary D.6.2 and Theorem D.6.3). We evaluate Theorem D.6.3 on the mean bounds \(\lambda_0,\dots,\lambda_k\) that Connected Dominating Set provides. By the mean number of terminals (Lemma 5.11), a uniform \(j\)-subset of a connected dominating set of size \(k\) leaves on average at most \(n-1-j(n-2)/k\) terminals; with the empty sample, which leaves all \(n\) vertices as terminals, this gives the bounds \(\lambda_0=n\) and \(\lambda_j=n-1-j(n-2)/k\) for \(1\le j\le k\).
Corollary 9.3 (The mean bounds of Connected Dominating Set). Let \(n\) be even, \(k=n/2\), \(\lambda_0=n\) and \(\lambda_j=n-1-j(n-2)/k\) for \(1\le j\le k\). Every deterministic black-box algorithm that is correct for \(\mathcal{C}_{\mathrm{mean}}^{\mathrm{all}}(\lambda_0,\dots,\lambda_k)\) has cost at least \[\frac{2^{H(1/4)n}}{6(n+1)(n+2)}=\frac{(4\cdot3^{-3/4})^{n}}{6(n+1)(n+2)}\ge\frac{1.7547^{n}}{6(n+1)(n+2)}\] on some no-instance, while Algorithm MLS-\(\theta\) with the parameters of Corollary 4.3(1), which calls only \(\mathrm{COST}\) and \(\mathrm{EXT}\) and needs only the mean bounds \(\lambda_0,\dots,\lambda_k\) as parameters, decides the same class with one-sided error at cost \(\sqrt3^{\,n}n^{O(1)}\).
Corollary 9.3 is a statement about the abstract class, not about Connected Dominating Set: over all solution sizes, the randomized algorithm of Theorem 6.4 runs in time \(O(1.7449^n)\), and Section 10 solves Connected Dominating Set deterministically in time \(O(1.7361^n)\) (Theorem 10.4), by using the affine structure of the running-time exponent and not only its values.
Exponential moments.
For the exponential-moment theorem the lower bound is much larger: the cost of a deterministic black-box algorithm can come close to the cost \(\binom nk\) of testing every \(k\)-set with \(\mathrm{MEM}\).
Theorem 9.4 (Black-box lower bound for exponential moments). Let \(\psi\ge0\) and \(\Gamma\ge1\), and let \(\mathcal H\) be a deterministic black-box algorithm that is correct for \(\mathcal{C}_{\mathrm{exp}}(\psi,\Gamma)\). Call a level \(t\in\{0,\dots,k\}\) feasible if \(J_t:=\lceil\binom nt2^{-\psi n}/\Gamma\rceil\le\binom kt/2\). Then for every feasible \(t\), the cost of \(\mathcal H\) on the no-instance \(\mathcal{F}=\emptyset\), \(g\equiv n\), is at least \(\frac13\min\{\binom nk,\binom nt\}\).
The strongest bound comes from the largest feasible \(t\); for Algorithm RS-\(\theta\) at the solution fraction \(k/n\approx0.4173\), where its running-time bound is attained (Table 3), it is numerically about \(1.9440^{n}\) (Appendix F), against \(O(1.7204^{n})\) for the randomized algorithm; this value is not used later.
We conjecture that the same planting argument, combined with Yao’s principle, shows that Theorem 4.1 is optimal up to polynomial factors also for randomized black-box algorithms, in analogy with the oracle lower bounds of (Esmer et al. 2024, 2026).
9.3 Balanced set-inclusion families
The structured derandomization replaces random samples by a family that contains, inside every solution, a sample of at least average weight, for every nonnegative weighting at once. We allow several classes of solution elements, because Theorem 9.10 needs two.
Definition 9.5 (Balanced family). Let \(|U|=n\) and \(\mathsf r\ge1\), let \(k_1,\dots,k_{\mathsf r}\ge0\) be integers with \(\sum_jk_j\le n\), and let \(t_j\) be integers with \(0\le t_j\le k_j\); put \(t=\sum_jt_j\). A family \(\mathcal B\subseteq\binom Ut\) is \((n;k;t)\)-balanced if for all pairwise disjoint \(S_1,\dots,S_{\mathsf r}\subseteq U\) with \(|S_j|=k_j\) and every \(w\colon\bigcup_jS_j\to\mathbb{R}_{\ge0}\), some \(X\in\mathcal B\) satisfies \(X\subseteq\bigcup_jS_j\), \(|X\cap S_j|=t_j\) for all \(j\), and \[w(X\cap S_j)\ \ge\ \frac{t_j}{k_j}\,w(S_j)\qquad\text{for every $j$ with $k_j\ge1$.}\] For \(\mathsf r=1\) we say \((n,k,t)\)-balanced.
An \((n,k,t)\)-balanced family is in particular an \((n,k,t)\)-set-inclusion family (Definition 9.1).
The construction partitions the universe into blocks of size about \(\log n/\log\log n\), guesses how the unknown solution classes meet the blocks, distributes the targets proportionally, and covers each block greedily by subsets that capture their proportional share of every weighting; the details and the proof of the following theorem are in Appendix D.7.
Theorem 9.6 (Balanced families in polynomial space). Fix \(\mathsf r\ge1\). Let \(n\ge16\) and \(\iota=\max(2,\lfloor\log n/\log\log n\rfloor)\). A deterministic algorithm, given \(k_1,\dots,k_{\mathsf r}\) and \(t_1,\dots,t_{\mathsf r}\) as in Definition 9.5, lists (possibly with repetitions) the members of an \((n;k;t)\)-balanced family \(\mathcal B\) with \[|\mathcal B|\ \le\ \iota^{12\mathsf r(n/\iota+1)}\,\frac{\binom nt}{\prod_j\binom{k_j}{t_j}} \ =\ \frac{\binom nt}{\prod_j\binom{k_j}{t_j}}\,2^{O(\mathsf rn(\log\log n)^{2}/\log n)} .\] It runs in time \(n^{O(1)}\) times this bound, plus \(n^{O(1)}\), and in space \(n^{O(1)}\).
For \(n<16\) the family \(\binom Ut\) is balanced (for each class take the \(t_j\) elements of \(S_j\) of largest weight) and has at most \(2^{15}\) members, so the theorem holds for all \(n\) after a constant change in the bound. For \(\mathsf r=1\) the size is optimal up to the factor \(2^{O(n(\log\log n)^{2}/\log n)}\), since every \((n,k,t)\)-set-inclusion family has at least \(\binom nt/\binom kt\) members (Section 9.1).
9.4 Exponential moments of integer affine certificates
The balanced families apply to running-time exponents with an affine certificate: a solution \(S\in\mathcal{F}_I\) with \(|S|=k\) for which some weights \(w\colon S\to\mathbb{R}_{\ge0}\), which may depend on \(S\) and need not be computable, and a constant \(\alpha\) satisfy \(g(I,X,k)\le\alpha-w(X)\) for the samples \(X\subseteq S\) in question, where only \(\alpha\) and a bound \(\Xi\) on the total weight \(w(S)\) are known to the algorithm. The exponential-moment theorem can exploit such a certificate more strongly than the mean-exponent theorem, because \(\mu_t(S)\) sees the whole distribution of \(w(X)\) and not only its mean. We first show that if the weights may be arbitrary nonnegative reals, then in the worst case this certifies no smaller running-time bound than the mean-exponent theorem, and then that for integer weights it certifies a smaller one, and that this smaller bound can be achieved deterministically.
Forms of the certificate.
Theorem 9.10 below tries every sample size \(t\ge1\) and needs \(g(I,X,k)\le\alpha-w(X)\) for every nonempty \(X\subseteq S\). The empty sample is excluded because the algorithm never lists it and because the inequality can fail there: for Connected Dominating Set, \(\alpha=n-1\) while the empty sample leaves all \(n\) vertices as terminals (Lemma 5.10 and (13)). It needs \(w(S)=\Xi\) rather than \(w(S)\ge\Xi\). This is no restriction, since lowering integer weights until the total is \(\Xi\) keeps it a certificate. And it needs integer weights, because only for them does the exponential-moment bound of the surrogate gain over its mean-exponent bound (Proposition 9.8).
Let \(S\) with \(|S|=k\) have an affine certificate \(g(I,X,k)\le\alpha-w(X)\) for all nonempty \(X\subseteq S\), with \(w(S)=\Xi\). The surrogate exponent \(\alpha-w(X)\) is defined for every \(X\subseteq S\), including \(X=\emptyset\), and the generating function of Definition 3.3 for the surrogate exponent is \[W_S(y)=\sum_{X\subseteq S}y^{|X|}2^{-\alpha+w(X)}=2^{-\alpha}\prod_{u\in S}\bigl(1+y2^{w(u)}\bigr).\] Lemma 9.7 finds, for every \(y\) at once, the weight profile that minimizes this product, and hence \(W_S(y)\).
Lemma 9.7 (Chord lemma). Let \(k\ge1\), let \(\Xi\ge0\) be an integer, \(a=\lfloor\Xi/k\rfloor\), \(k_{a+1}=\Xi-ak\) and \(k_a=k-k_{a+1}\). Let \(v\in\mathbb{R}^{k}\) have \(\sum_uv_u=\Xi\) and no entry in the open interval \((a,a+1)\). Then for every \(y>0\), \[\prod_u\bigl(1+y2^{v_u}\bigr)\ \ge\ \mathsf P^*(y):=\bigl(1+y2^{a}\bigr)^{k_a}\bigl(1+y2^{a+1}\bigr)^{k_{a+1}} .\] Without the restriction on the entries, \(\prod_u(1+y2^{v_u})\ge(1+y2^{\Xi/k})^{k}\).
With the chord lemma we can compare the two theorems on the surrogate exponent.
Proposition 9.8 (Real weights give only the mean-exponent bound). Let \(S\) be a \(k\)-subset of a universe of size \(n\), with \(k\ge1\), and let \(\alpha\) be real and \(\Xi\ge0\). For \(w\colon S\to\mathbb{R}_{\ge0}\) with \(w(S)=\Xi\) let \(\mu^w_t(S)=\sum_{X\in\binom St}2^{-\alpha+w(X)}\) for \(0\le t\le k\), the exponential moments of the surrogate exponent \(\alpha-w(X)\), and put \(\mathsf R(w)=\min_{0\le t\le k}\binom nt/\mu^w_t(S)\). Let \(\bar w\equiv\Xi/k\) be the uniform profile. Then \(\mathsf R(\bar w)=\min_{0\le t\le k}\binom nt\binom kt^{-1}2^{\alpha-t\Xi/k}\), and \(\mathsf R(w)\le(n+1)\,\mathsf R(\bar w)\) for every such \(w\). If \(\Xi\) is an integer and \(w^*\) is the profile of Lemma 9.7, then \(\mathsf R(w)\le(n+1)\,\mathsf R(w^*)\) for every such \(w\) with integer values.
Here \(\mathsf R(w)\) is the smallest running-time bound \(2^{\psi n}\) that Theorem 3.5 with \(\Gamma=1\) certifies for \(S\) through the surrogate exponent, and \(\mathsf R(\bar w)\) is the running-time bound of Theorem 4.1 with mean bound \(\alpha-t\Xi/k\), without its polynomial factor.
So in the worst case over real weights the affine surrogate certifies, through Theorem 3.5, no smaller running-time bound than the mean-exponent theorem. For Connected Dominating Set the weights of Lemma 5.10, the degrees minus one of the vertices of the solution in a spanning tree, are integers, and for the worst integer profile the running-time bound certified through Theorem 3.5 is exponentially smaller than that of the mean-exponent theorem (Section 10). The following algorithm derandomizes the exponential-moment bound for the worst integer profile. It splits the unknown solution into a light class (weights at most \(a\)) and a heavy class (weights at least \(a+1\)), guesses the sizes and total weights of the two classes, and runs a two-class balanced family for each guess.
Algorithm 9.9 (Integer affine certificates). \((I,k)\) together with a rational \(\alpha\) and an integer \(\Xi\ge0\). Put \(a=\lfloor\Xi/k\rfloor\). If \(\alpha<\Xi\), answer no. Otherwise run the following for every guess \((k^-,\Xi^-)\) of integers with \(1\le k^-\le k\) and \(0\le\Xi^-\le ak^-\), where \(k^+:=k-k^-\) and \(\Xi^+:=\Xi-\Xi^-\), subject to \[\Xi^+\ge(a+1)k^+\ \text{ if }k^+\ge1,\qquad\Xi^+=0\ \text{ if }k^+=0 .\]
(1) Put \(\bar w^-=\Xi^-/k^-\) and, if \(k^+\ge1\), \(\bar w^+=\Xi^+/k^+\). (If \(k^+=0\) the heavy class is omitted, \(t^+=0\), and \(\bar w^+\) is not used.)
(2) Choose integers \(0\le t^-\le k^-\) and \(0\le t^+\le k^+\) with \(t:=t^-+t^+\ge1\) that minimize \(\binom nt\big/\left(\binom{k^-}{t^-}\binom{k^+}{t^+}\right)\cdot2^{\theta}\), where \(\theta:=\alpha-t^-\bar w^--t^+\bar w^+\), up to a factor \(2\), by taking a minimizer of approximations of the logarithms of the candidates to within \(\frac14\).
(3) List the two-class \((n;k^-,k^+;t^-,t^+)\)-balanced family of Theorem 9.6 (a one-class family if \(k^+=0\)).
(4) For each listed \(X\), compute \(g(I,X,k)\); if \(g(I,X,k)\le\theta\), run \(\mathcal{A}\) on \((I,X,k)\) and answer yes if it accepts.
After all guesses, answer no.
The condition \(\Xi^+=0\) for \(k^+=0\) matters: without it, a guess with \(k^+=0\) and \(\Xi^-<\Xi\) would run a one-class family with mean \(\bar w^-<\Xi/k\), and hence a larger threshold \(\theta\). Since every guess is run, this guess, which takes time about \(2^{n}\) for the parameters of Section 10, would dominate the total. Algorithm 9.9 has the following guarantee.
Theorem 9.10 (Deterministic exponential moments of integer affine certificates). Let \(k\ge1\), a rational \(\alpha=\alpha(I,k)\) and an integer \(\Xi=\Xi(I,k)\) with \(0\le\Xi\le N^{O(1)}\) be computable in time \(N^{O(1)}\). Say that \(S\in\mathcal{F}_I\) with \(|S|=k\) has an integer certificate if some \(w\colon S\to\mathbb Z_{\ge0}\) with \(w(S)=\Xi\) satisfies \[g(I,X,k)\le\alpha-w(X)\qquad\text{for every nonempty }X\subseteq S .\] Put \(a=\lfloor\Xi/k\rfloor\), \(k_{a+1}=\Xi-ak\), \(k_a=k-k_{a+1}\) and \(\mathsf P^*(y)=(1+y2^{a})^{k_a}(1+y2^{a+1})^{k_{a+1}}\). Algorithm 9.9 is deterministic, answers no if \(\mathcal{F}_I\) has no set of size at most \(k\), and answers yes if some \(S\in\mathcal{F}_I\) with \(|S|=k\) has an integer certificate. It runs in time \[N^{O(1)}\,2^{O(n(\log\log n)^{2}/\log n)}\, \max\Bigl(1,\ \inf_{y>0}\frac{\bigl((1+y)^{n}-1\bigr)\,2^{\alpha}}{\mathsf P^*(y)-1}\Bigr)\] and in space \(N^{O(1)}\) plus the space of \(\mathcal{A}\).
The maximum with \(1\) in the time bound covers the early answer no and the polynomial bookkeeping; the infimum alone can be smaller than \(1\) when \(\alpha<\Xi\). The hypothesis that \(\alpha\) is rational makes the test \(\alpha<\Xi\) and the comparisons with \(\theta\) exact; a real \(\alpha\) is replaced by a rational \(\hat\alpha\) with \(\alpha\le\hat\alpha\le\alpha+1\), which preserves every integer certificate and at most doubles the time.
The proof of Theorem 9.10 is in Appendix D.8.1, with those of Lemma 9.7 and Proposition 9.8. It shows that the guess formed by the light and heavy classes of an integer certificate is tried, that the balanced family for this guess contains a nonempty sample whose weight is at least its proportional share, and it bounds the running time of each guess by expanding the product over a two-valued weight profile and applying Lemma 9.7.