Live ReciprocalTest execution makes oracle-call progress
ProvedCountingLLL.ReciprocalTest.oracle_progressalgorithmsprobability
At every finite time when the operational ReciprocalTest has not halted, its oracle-call counter is at least . Equivalently, . This pathwise progress bound implies that any nonhalting execution makes infinitely many oracle calls.
Preamble
import Definitions.Def_CountingLLL_ReciprocalTest open CountingLLL.ReciprocalTest
Formal statement
theorem CountingLLL.ReciprocalTest.oracle_progress (ω : Entropy) (n : ℕ)
(hlive : (run ω n).phase ≠ .done false ∧ (run ω n).phase ≠ .done true) :
n ≤ 4*(run ω n).oracleUsed+1 := by sorrySource
Liu, Wang, Yin, Zhang and Zhou, A Counting and Sampling Lovász Local Lemma, STOC #442, Algorithm 6, pp. 27–28, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/442.pdf