Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.5 — a (1/2−ϵ)(1/2-\epsilon)(1/2−ϵ)-approximation for monotone submodular maximization under a matroid constraint in O~(n1/3/ϵ3)\tilde O(n^{1/3}/\epsilon^3)O~(n1/3/ϵ3) rounds

Open
ParallelMatroidBasis.Main.Supplement.theorem_1_5

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

matroidsp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1parallel-algorithmsquery-complexitysubmodular-optimization

There is an exponent k∈Nk\in\mathbb Nk∈N such that for every c>0c>0c>0 there are constants C>0C>0C>0 and d∈Nd\in\mathbb Nd∈N such that for every ε>0\varepsilon>0ε>0 there is one randomized parallel algorithm AεA_\varepsilonAε​ — one procedure for every ground-set size nnn, seeing a matroid M=(E,I)M=(E,\mathcal I)M=(E,I) on E=[n]E=[n]E=[n] only through independence queries and a set function fff only through value queries — such that for all nnn, every such matroid MMM and every monotone submodular f:2E→R≥0f:2^E\to\mathbb R_{\ge0}f:2E→R≥0​ (A⊆B⇒f(A)≤f(B)A\subseteq B\Rightarrow f(A)\le f(B)A⊆B⇒f(A)≤f(B); f(A)+f(B)≥f(A∪B)+f(A∩B)f(A)+f(B)\ge f(A\cup B)+f(A\cap B)f(A)+f(B)≥f(A∪B)+f(A∩B)):

  1. every run uses at most C (1+n1/3(log⁡2(n+2))k/ε3)C\,\big(1+n^{1/3}(\log_2(n+2))^k/\varepsilon^3\big)C(1+n1/3(log2​(n+2))k/ε3) adaptive rounds;
  2. every run makes at most (n+1)d(n+1)^d(n+1)d independence queries to MMM and at most (n+1)d(n+1)^d(n+1)d queries to fff in total;
  3. if n≥1n\ge1n≥1, with probability at least 1−n−c1-n^{-c}1−n−c the output SSS satisfies
S∈Iandf(S) ≥ (12−ε)max⁡T∈If(T).S\in\mathcal I\qquad\text{and}\qquad f(S)\ \ge\ \Big(\tfrac12-\varepsilon\Big)\max_{T\in\mathcal I}f(T).S∈Iandf(S) ≥ (21​−ε)T∈Imax​f(T).

The constants CCC, ddd and the exponent kkk do not depend on ε\varepsilonε. This improves the O~(n3/7/ε3)\tilde O(n^{3/7}/\varepsilon^3)O~(n3/7/ε3) rounds of [KPS26] for the independence-query model; no normalization f(∅)=0f(\emptyset)=0f(∅)=0 is assumed.

Formalization Note The query model is MultiOracle's SubmodAlgorithm. Monotonicity and submodularity reuse the published SubsamplingSM.Offline.IsMonotoneSetFn and NonmonotoneSubmod.Shared.Submodular; nonnegativity is a separate hypothesis. The maximum is encoded as "f(S)≥(1/2−ε)f(T)f(S)\ge(1/2-\varepsilon)f(T)f(S)≥(1/2−ε)f(T) for every independent TTT". O~\tilde OO~ is read as a fixed power of log⁡2(n+2)\log_2(n+2)log2​(n+2), "with high probability" as failure at most n−cn^{-c}n−c for every c>0c>0c>0.

Differences from the source:

  • encoding: an algorithm making rounds of polynomially many queries → one ExactParallelSampling.QuasiUniform.Protocol (Finset (Fin n) ⊕ Finset (Fin n)) (Bool ⊕ ℝ) (Finset (Fin n)) for every n, with a uniform [0,1]^ℕ tape and measurable next-action maps; reason: the batches and the output depend only on the tape and on earlier answers; a tape of uniform reals simulates any finite random choice, and measurability only restricts the algorithm to be exhibited
  • encoding: a matroid M on n elements → a Matroid (Fin n) with ground set univ; reason: the algorithm knows the n labels of the ground set, as in the source's oracle model (same convention as the base mission)
  • encoding: a monotone submodular function f : 2^E → R≥0, accessed by queries → f : Finset (Fin n) → ℝ with IsMonotoneSetFn f, Submodular f (lattice inequality) and 0 ≤ f S for all S; value queries return f(T) exactly; reason: the source's three conditions, with no normalization f(∅) = 0, as in the source
  • reading: for any ε > 0, an Õ(n^{1/3}/ε^3) round algorithm → ∃ k : ℕ, then for each c ∃ C > 0 and d, then for each ε > 0 an algorithm with at most C(1 + n^{1/3}(log₂(n+2))^k/ε³) rounds on every run; reason: Õ hides a polylogarithmic factor in n; C, d, k uniform in ε is the stronger reading (the O(·) keeps 1/ε³ explicit); log₂(n+2) ≥ 1 keeps the factor defined at n ≤ 1
  • reading: polynomially many independence queries to M and polynomially many queries to f → at most (n+1)^d independence queries and at most (n+1)^d value queries over the whole run, d independent of ε; reason: the source states query totals, not per-round counts; a total bound is the stronger reading and implies a per-round bound
  • reading: with high probability → for every c > 0 (with constants and algorithm depending on c), for n ≥ 1 the success probability is at least 1 − n^{−c}; reason: the base mission's reading of the paper's 'with high probability'; the proofs amplify to inverse-polynomial failure for an arbitrary exponent (PDF pp.37, 41); this is the stronger reading
  • encoding: S ∈ I with f(S) ≥ (1/2 − ε) max_{T∈I} f(T) → M.Indep S and (1/2 − ε) f(T) ≤ f(S) for every independent T; reason: the maximum over the finite nonempty family I is attained, so the two conditions coincide
Preamble
import Mathlib
import Definitions.Def_NonmonotoneSubmod_Shared_Submodular
import Definitions.Def_SubsamplingSM_Offline_IsMonotoneSetFn
import Definitions.Def_ParallelMatroidBasis_Main_Supplement_MultiOracle

noncomputable section
open Classical MeasureTheory
Formal statement
namespace ParallelMatroidBasis.Main.Supplement

/-- Theorem 1.5, PDF p.5 (printed p.3), with `Õ(·)` read as a polylogarithmic factor
`(log₂ (n+2))^k` and "with high probability" as failure probability at most `n^{−c}` for every
fixed `c > 0`. There is `k` such that for every `c > 0` there are `C > 0` and `d` such that for
every `ε > 0` there is one parallel algorithm `A` (a protocol for every `n`, seeing `M` only
through independence queries and `f` only through value queries) such that for all `n`, every
matroid `M` on `Fin n` and every monotone submodular `f : 2^{Fin n} → ℝ≥0`: every run uses at most
`C (1 + n^{1/3} (log₂ (n+2))^k / ε³)` rounds, at most `(n+1)^d` independence queries and at most
`(n+1)^d` value queries in total, and for `n ≥ 1`, with probability at least `1 − n^{−c}`, the
output `S` is independent and `f(S) ≥ (1/2 − ε) max_{T ∈ I} f(T)`. -/
theorem theorem_1_5 :
    ∃ k : ℕ, ∀ c : ℝ, 0 < c →
      ∃ (C : ℝ) (d : ℕ), 0 < C ∧ ∀ ε : ℝ, 0 < ε →
        ∃ A : SubmodAlgorithm,
          ∀ (n : ℕ) (M : Matroid (Fin n)) (f : Finset (Fin n) → ℝ), M.E = Set.univ →
            SubsamplingSM.Offline.IsMonotoneSetFn f → NonmonotoneSubmod.Shared.Submodular f →
            (∀ S, 0 ≤ f S) →
            RunRoundsAtMost (A n) (submodOracle M f)
              (C * (1 + (n : ℝ) ^ ((1 : ℝ) / 3) * (Real.logb 2 ((n : ℝ) + 2)) ^ k / ε ^ 3)) ∧
            RunTotalQueriesAtMost (A n) (submodOracle M f) IsIndepQuery ((n + 1) ^ d) ∧
            RunTotalQueriesAtMost (A n) (submodOracle M f) IsValueQuery ((n + 1) ^ d) ∧
            (1 ≤ n → ENNReal.ofReal (1 - (n : ℝ) ^ (-c)) ≤ submodSuccessProb A n M f ε)
      := by sorry

end ParallelMatroidBasis.Main.Supplement
Source
Aaron Putterman, Sanjeev Khanna, Junkai Song, STOC 2027 submission #589 (October 2026), A Near-Optimal Parallel Algorithm for Finding Matroid Bases, PDF sha256 71ee2ac010ac681077fc3191139efe918fa4a9b8c6dad648fac2ec33016764d6, Theorem 1.5, p.3 (PDF p.5); proof via Lemma B.2 and Lemma B.3 ([BRS19b]), p.35 (PDF p.37)

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