Appendix B Related mechanisms
This appendix compares the probabilistic core of Theorem 3.5 with related mechanisms outside Monotone Local Search, and its generating function with earlier uses in Monotone Local Search (Section 1.3).
Restarts with a cutoff.
Luby, Sinclair and Zuckerman (Luby, Sinclair, and Zuckerman 1993) analyzed restart strategies for Las Vegas algorithms, in which runs are cut off after a prescribed number of steps and restarted; (Alt et al. 1996) truncate runs to obtain small tail probabilities. Skipping samples whose running-time exponent exceeds a threshold is this mechanism.
The Markov cutoff.
Zamir (Zamir 2023 Lemma 2) shows that a Las Vegas algorithm whose running time, conditioned on a random variable \(Y\), is \(2^Y\) in expectation can be run in expected time \(O(2^{\mathbb{E}[Y]}\cdot\mathbb{E}[Y])\) when \(\mathbb{E}[Y]\) is known, by repeating runs truncated at the threshold \(\mathbb{E}[Y]+1\) and applying Markov’s inequality. The Markov-cutoff algorithm of Remark 4.2, which gives the mean-exponent theorem (Theorem 4.1) directly, is this mechanism transplanted into Monotone Local Search, with the same polynomial factor in the running time. Zamir’s main theorem (Zamir 2023 Theorem 1) removes the polynomial factor and the knowledge of the distribution, giving \(O(2^{\mathbb{E}[Y]})\); Zamir states it with base \(e\), and it gives this form when applied to \(X=Y\ln2\), as \(2^Y=e^{X}\). Theorem 3.5 differs in what it is compared with: up to polynomial factors its running-time bound is \(1/\mathbb{E}[2^{-g}]\), which is at most \(2^{\mathbb{E}[g]}\) by Jensen’s inequality and can be exponentially smaller.
Exponential moments for restart strategies.
Scaman (Scaman 2023 Lemma 4) shows that for a Las Vegas algorithm with running time \(\mathrm{rt}\in[1,\infty]\) the best expected running time of a restart strategy lies between \(1/\mathbb{E}[1/\mathrm{rt}]\) and \(e^2\bigl(1+\ln(1/\mathbb{E}[1/\mathrm{rt}])\bigr)/\mathbb{E}[1/\mathrm{rt}]\). For one sample size \(t\), put \(\mathrm{rt}=2^{g(I,X,k)}\) if a uniform \(t\)-subset \(X\) of the universe lies in the solution \(S\) and \(\mathrm{rt}=\infty\) otherwise; then \(\mathbb{E}[1/\mathrm{rt}]=\mu_t(S)/\binom nt\). So Scaman’s Lemma 4 is the restart-strategy analogue of the probabilistic core of Theorem 3.5: its lower bound corresponds to Theorem 3.12(a), and its upper bound to Theorem 3.5 for one fixed \(t\), with each run cut off after the running time that its threshold allows in place of a computed running-time exponent. Scaman bounds the expected running time, whereas we bound the success probability within a fixed budget; the two forms convert into each other up to constant factors (by Markov’s inequality, expected time \(T\) gives success probability at least \(1/2\) within budget \(2T\); conversely, success probability \(p\) within budget \(B\) gives expected time at most \(B/p\) by independent restarts). His upper bound has the factor \(e^2(1+\ln(1/\mathbb{E}[1/\mathrm{rt}]))\) where our threshold lemma (Lemma 3.8) has a factor linear in the largest threshold; both are polynomial. Scaman’s impossibility result for universal strategies, which use one cutoff sequence for every distribution, concerns a different question, since our algorithm is given its target running time \(2^{\psi n}\).
Exponential moments in exact algorithms.
As Zamir (Zamir 2023) discusses, the success probability of the PPSZ algorithm of (Paturi et al. 2005) is an exponential moment \(\mathbb{E}[2^{-G}]\) of the number \(G\) of guessed variables, which Jensen’s inequality bounds from below by \(2^{-\mathbb{E}[G]}\). The normalized moments \(\mu_t(S)/\binom nt=\mathbb{E}\left[\mathbf 1[X\subseteq S]\,2^{-g(I,X,k)}\right]\), for a uniform \(t\)-subset \(X\) of the universe and with \(\mathbf 1[X\subseteq S]\) equal to \(1\) if \(X\subseteq S\) and \(0\) otherwise, have the same form.
Generating functions.
(Fomin et al. 2019) and Gaspers and Lee (Gaspers and Lee 2017) already used generating functions in Monotone Local Search, for product-form running times, in particular a negative-binomial series in \(k-t\) followed by the binomial theorem. Our \(W_S(y)\) is a different series, the binomial series over the subsets of one solution, and it is defined for arbitrary running-time exponents; the comparison \(W_S(y)\le\max_t(\mu_t(S)/\binom nt)(1+y)^n\) in the proof of Theorem 3.5 is what makes it usable.
Summary.
Table 5 summarizes which features of our setting the mechanisms above have. The features are the five of the paragraph “What is new compared with restarts and cutoffs” in Section 1: (i) the running time of a call is computed before the call, so a call above the threshold is skipped rather than cut off; (ii) a call can succeed only if the sample lies in an unknown solution; (iii) the running time depends on the structure of the sample, not only on its size; (iv) one generating function covers all sample sizes; and (v) that generating function is bounded by combinatorial recursions over the sampled structure.
| Mechanism | (i) | (ii) | (iii) | (iv) | (v) |
|---|---|---|---|---|---|
| Restarts with a cutoff (Luby, Sinclair, and Zuckerman 1993; Alt et al. 1996) | no | no | no | – | no |
| Markov cutoff (Zamir 2023) | no | no | no | – | no |
| Restart strategies via \(\mathbb{E}[1/\mathrm{rt}]\) (Scaman 2023) | no | no | no | – | no |
| Monotone Local Search, product form (Fomin et al. 2019; Gaspers and Lee 2017) | yes | yes | no | yes | no |
| Theorem 3.5 with Lemma 3.9 | yes | yes | yes | yes | yes |