Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.8 — Randomized k-OV running-time lower bound

Open
NearLogSetCover966.Main.Supplement.theorem_4_8

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parameterized-complexityset-cover

Assuming exactly the randomized logarithmic-dimension kkk-OV hypothesis, there are absolute constants α,ε>0\alpha,\varepsilon>0α,ε>0 such that for every computable parameter factor TTT, no two-sided bounded-error randomized algorithm solves

αlog⁡2NK2log⁡2log⁡2N-gap K-Set Cover\frac{\alpha\log_2N}{K^2\log_2\log_2N}\text{-gap }K\text{-Set Cover}K2log2​log2​Nαlog2​N​-gap K-Set Cover

on NNN indexed sets with universe size at most NNN, within T(K)NεKT(K)N^{\varepsilon K}T(K)NεK actual worst-case time. Success must be at least 2/32/32/3 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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me