Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Polynomial-accuracy LOCAL matching booster with physical round accounting

Proved
FasterDistributedMatching.ApproximateMatching.fmu_local_booster

by Shuze Chen · Nov 17, 2026 · Mathlib 0df444a (Lean v4.33.1)

distributed-algorithmsgraph-theorymatching

Fix a constant approximation fraction c∈(0,1]c\in(0,1]c∈(0,1]. There are positive integers p,Cp,Cp,C, depending only on ccc, that implement the Fischer--Mitrović--Uitto matching booster in the synchronous deterministic LOCAL model.

Fix a polynomial identifier convention bbb and a protocol AAA that, on every bounded finite simple graph with identifiers below max⁡{2,n}b+4\max\{2,n\}^{b+4}max{2,n}b+4, reports an actual matching of size at least ccc times the optimum. Then there is one protocol BBB, fixed before network inputs and the integer accuracy parameter qqq, that for every q≥2q\ge2q≥2 reports a matching MMM satisfying

OPT⁡(G)≤(1+1/q)∣M∣.\operatorname{OPT}(G)\le(1+1/q)|M|.OPT(G)≤(1+1/q)∣M∣.

Write TA(n,Δ)T_A(n,\Delta)TA​(n,Δ) for the round count of AAA with common bounds (n,Δ)(n,\Delta)(n,Δ). Protocol BBB satisfies

TB(n,Δ,q)≤C(q+1)p(TA((n+1)(q+1)p,(Δ+1)(q+1)p)+(q+1)p).T_B(n,\Delta,q)\le C(q+1)^p\left(T_A\big((n+1)(q+1)^p,(\Delta+1)(q+1)^p\big)+(q+1)^p\right).TB​(n,Δ,q)≤C(q+1)p(TA​((n+1)(q+1)p,(Δ+1)(q+1)p)+(q+1)p).

The input to BBB consists of the common bounds and qqq, the processor's own identifier, and its neighbor identifiers; its identifiers need only be below max⁡{2,n}b+1\max\{2,n\}^{b+1}max{2,n}b+1. All simulated communication is charged in physical rounds, and all private tapes are ignored. This separates the booster from the construction and time analysis of a constant-approximation oracle.

Formalization Note This is the LOCAL specialization of the framework, with reciprocal integer accuracy, one polynomial padding large enough for all auxiliary graph sizes, degrees, routes and processing times, and a common padded bound used for every oracle invocation. Specializing the source parameter to 1/(2q)1/(2q)1/(2q) gives the stated approximation factor.

Preamble
import Mathlib
import Definitions.Def_FasterDistributedMatching_ApproximateMatching_Local
open FasterDistributedMatching.ApproximateMatching
Formal statement
theorem FasterDistributedMatching.ApproximateMatching.fmu_local_booster :
    ∀ c : ℝ, 0 < c → c ≤ 1 →
      ∃ p C : ℕ, 1 ≤ p ∧ 0 < C ∧
        ∀ (b : ℕ) (A : Deterministic Bounds (Finset ℕ) (Option ℕ)),
          (∀ (N : ℕ) (G : SimpleGraph (Fin N)) (k : Bounds),
            boundedGraph G k.n k.degree →
            ∀ ids : Fin N → ℕ, Identifiers k.n (b+4) ids →
              ∃ M : SimpleGraph (Fin N),
                ReportsMatching G ids (execute A G k ids (neighborIDs G ids)) M ∧
                c*(optimum G:ℝ) ≤ (matchingSize M:ℝ)) →
          ∃ B : Deterministic (Bounds × ℕ) (Finset ℕ) (Option ℕ),
            (∀ (k : Bounds) (q : ℕ), 2 ≤ q →
              B.program.rounds (k,q) ≤ C*(q+1)^p*
                (A.program.rounds ⟨(k.n+1)*(q+1)^p,(k.degree+1)*(q+1)^p⟩+(q+1)^p)) ∧
            ∀ (N : ℕ) (G : SimpleGraph (Fin N)) (k : Bounds) (q : ℕ),
              2 ≤ q → boundedGraph G k.n k.degree →
              ∀ ids : Fin N → ℕ, Identifiers k.n (b+1) ids →
                ∃ M : SimpleGraph (Fin N),
                  ReportsMatching G ids (execute B G (k,q) ids (neighborIDs G ids)) M ∧
                  (optimum G:ℝ) ≤ (1+1/(q:ℝ))*(matchingSize M:ℝ) := by sorry
Source
Fischer--Mitrović--Uitto, Deterministic (1+epsilon)-Approximate Maximum Matching with poly(1/epsilon) Passes in the Semi-Streaming Model and Beyond, https://arxiv.org/pdf/2106.04179, Theorem 1.2 (PDF p.3), Theorem 6.1 and Sections 6.1--6.7 (PDF pp.26--32), including the bounded-loop remark after Theorem 6.1. LOCAL specialization used by Ghaffari--Grunau submission #1024, Section 3.5, printed p.15 / PDF p.17.

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