Theorem 3.1 (Simulation Theorem) — when
ProvedDistVerif.Simulation.theorem_3_1Let be natural numbers with , let , and let . Consider the network of §3.1 in the B model, with Alice's input at and Bob's input at . Suppose a public-coin randomized distributed algorithm on computes with -error (both and output with probability at least , for every input) within rounds, where
Then there is a public-coin two-party protocol that computes with -error using at most
bits of communication. In terms of complexities: if , then
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 's communication through the tree edges per round.
Formalization Note "Within rounds" means the outputs of and are read after exactly 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 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 ; the "in other words" inequality between the minima is the corresponding statement about complexities. The hypothesis is needed to name and ; when the hypothesis cannot hold, and with forces , hence . is arbitrary (the paper assumes ; at the function is constant and the theorem still holds).
import Mathlib import Definitions.Def_DistVerif_Simulation_Network import Definitions.Def_DistVerif_Simulation_Algorithm import Definitions.Def_DistVerif_Simulation_Protocol
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.