Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.1 (Simulation Theorem) — Rϵcc−pub(f)≤2dpB RϵG(Γ,d,p)(f)R^{cc-pub}_\epsilon(f)\le 2dpB\,R^{G(\Gamma,d,p)}_\epsilon(f)Rϵcc−pub​(f)≤2dpBRϵG(Γ,d,p)​(f) when RϵG(Γ,d,p)(f)<(dp−1)/2R^{G(\Gamma,d,p)}_\epsilon(f)<(d^p-1)/2RϵG(Γ,d,p)​(f)<(dp−1)/2

Proved
DistVerif.Simulation.theorem_3_1

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

communication-complexitydistributed-computinglower-boundsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let Γ,d,p,B,b\Gamma,d,p,B,bΓ,d,p,B,b be natural numbers with dp≥1d^p\ge1dp≥1, let ϵ≥0\epsilon\ge0ϵ≥0, and let f:{0,1}b×{0,1}b→{0,1}f:\{0,1\}^b\times\{0,1\}^b\to\{0,1\}f:{0,1}b×{0,1}b→{0,1}. Consider the network G(Γ,d,p)G(\Gamma,d,p)G(Γ,d,p) of §3.1 in the B model, with Alice's input xxx at s=u0ps=u^p_0s=u0p​ and Bob's input yyy at r=udp−1pr=u^p_{d^p-1}r=udp−1p​. Suppose a public-coin randomized distributed algorithm on G(Γ,d,p)G(\Gamma,d,p)G(Γ,d,p) computes fff with ϵ\epsilonϵ-error (both sss and rrr output f(x,y)f(x,y)f(x,y) with probability at least 1−ϵ1-\epsilon1−ϵ, for every input) within TTT rounds, where

T<dp−12.T<\frac{d^p-1}{2}.T<2dp−1​.

Then there is a public-coin two-party protocol that computes fff with ϵ\epsilonϵ-error using at most

2 d p B T2\,d\,p\,B\,T2dpBT

bits of communication. In terms of complexities: if RϵG(Γ,d,p)(f)<(dp−1)/2R^{G(\Gamma,d,p)}_\epsilon(f)<(d^p-1)/2RϵG(Γ,d,p)​(f)<(dp−1)/2, then

Rϵcc−pub(f)≤2dpB RϵG(Γ,d,p)(f).R^{cc-pub}_\epsilon(f)\le 2dpB\,R^{G(\Gamma,d,p)}_\epsilon(f).Rϵcc−pub​(f)≤2dpBRϵG(Γ,d,p)​(f).

This is the Simulation Theorem of Das Sarma et al. Combined with lower bounds on the communication complexity of set disjointness and equality, it yields the lower bounds of §§4–7 for distributed verification and approximation problems: an algorithm faster than half the path length must squeeze fff's communication through the dpdpdp tree edges per round.

Formalization Note "Within TTT rounds" means the outputs of sss and rrr are read after exactly TTT rounds; this is equivalent to the paper's worst-case running time over inputs and random strings, since an algorithm that finishes earlier can idle. Messages are exactly BBB bits on every directed edge in every round. The protocol sends one bit per round, so its cost is the number of bits exchanged, as in §2.2. The theorem is stated for every algorithm and gives a protocol of cost k≤2dpBTk\le 2dpBTk≤2dpBT; the "in other words" inequality between the minima is the corresponding statement about complexities. The hypothesis dp≥1d^p\ge1dp≥1 is needed to name sss and rrr; when dp=1d^p=1dp=1 the hypothesis T<(dp−1)/2T<(d^p-1)/2T<(dp−1)/2 cannot hold, and T<(dp−1)/2T<(d^p-1)/2T<(dp−1)/2 with T≥0T\ge0T≥0 forces dp≥2d^p\ge2dp≥2, hence s≠rs\ne rs=r. bbb is arbitrary (the paper assumes b≥1b\ge1b≥1; at b=0b=0b=0 the function fff is constant and the theorem still holds).

Preamble
import Mathlib
import Definitions.Def_DistVerif_Simulation_Network
import Definitions.Def_DistVerif_Simulation_Algorithm
import Definitions.Def_DistVerif_Simulation_Protocol
Formal statement
namespace DistVerif.Simulation

/-- **Theorem 3.1 (Simulation Theorem)** (p. 1247). If a public-coin `ε`-error B-model
algorithm on `G(Γ, d, p)` computes `f` in `T < (d^p - 1)/2` rounds, then a public-coin
`ε`-error two-party protocol computes `f` with at most `2·d·p·B·T` bits of communication. -/
theorem theorem_3_1 (Γ d p B b : ℕ) (hdp : 0 < d ^ p) (ε : ℝ) (hε : 0 ≤ ε)
    (f : (Fin b → Bool) → (Fin b → Bool) → Bool) (T : ℕ)
    (hT : (T : ℝ) < ((d : ℝ) ^ p - 1) / 2) (A : PubAlg (Vtx Γ d p) B b)
    (hA : A.ComputesWithin (graph Γ d p) (sNode Γ d p hdp) (rNode Γ d p hdp) T f ε) :
    ∃ k : ℕ, k ≤ 2 * d * p * B * T ∧ ∃ P : PubProtocol b, P.ComputesWithin k f ε := by sorry

end DistVerif.Simulation
Source
Das Sarma, Holzer, Kor, Korman, Nanongkai, Pandurangan, Peleg, Wattenhofer, Distributed Verification and Hardness of Distributed Approximation, SIAM J. Comput. 41 (2012), p. 1247, Theorem 3.1 (Simulation Theorem); proof in §3.4, p. 1250
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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