Theorem 4.8 — Randomized k-OV running-time lower bound
OpenNearLogSetCover966.Main.Supplement.theorem_4_8p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover
Assuming exactly the randomized logarithmic-dimension -OV hypothesis, there are absolute constants such that for every computable parameter factor , no two-sided bounded-error randomized algorithm solves
on indexed sets with universe size at most , within actual worst-case time. Success must be at least on both promise branches. This is the conditional fine-grained companion result, separate from unconditional deterministic W[1]-hardness.
Formalization Note Binary encodings and the inherited finite incidence and actual-machine conventions are used. All resource witnesses are uniform as specified above.
Differences from the source:
- encoding: asymptotic time bound and meaningful gap range → computable exceptional-size threshold per parameter, N≥4 and gap≥1; reason: finite exceptional inputs can be decided directly; absolute time coefficients are absorbed in arbitrary computable T
- encoding: randomized k-OV Hypothesis 2.2 and bounded error → actual fresh-bit programs and literal quantifier order for Hypothesis 2.2; reason: the same operational cost and two-sided success model is used in the premise and lower bound
Preamble
import Definitions.Def_NearLogSetCover966_Main_Supplement_Promises set_option autoImplicit false
Formal statement
namespace NearLogSetCover966.Main.Supplement
/-- Theorem 4.8 (=1.4). The hypothesis is used only by this result. -/
theorem theorem_4_8 (H : RandomizedOVHypothesis) :
∃ α ε : ℝ, 0 < α ∧ 0 < ε ∧
∀ T : ℕ → ℕ, Computable T →
¬ ∃ (P : RandomProgram) (threshold : ℕ → ℕ),
Computable threshold ∧ FineSolver α ε T P threshold := by sorry
end NearLogSetCover966.Main.Supplement
Source
Bingkai Lin, Xin Zheng, STOC 2027 submission #966 (October 2026), Theorem 4.8, printed p.20 (PDF p.22)