Proof of Lemma 3.4 — for
ProvedDistVerif.Simulation.compl_R_subset_Lcommunication-complexitydistributed-computinglower-boundsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be the network of §3.1 with vertex set and -left and -right sets , , and let be an integer with . Then
The first inclusion is stated in the proof of Lemma 3.4 ("since and share some path vertices"); the second is its mirror image, used for equation (3.1), which the paper says "is proved in exactly the same way". Together they say that every vertex whose state Bob does not track is tracked by Alice and vice versa, so Alice can compute every message that crosses into Bob's region.
Formalization Note makes a genuine predecessor; at the inclusions concern and .
Preamble
import Mathlib import Definitions.Def_DistVerif_Simulation_Network
Formal statement
namespace DistVerif.Simulation
/-- **Proof of Lemma 3.4, second paragraph** (p. 1250). For `0 < t < (d^p - 1)/2`,
`V \ R_{t-1} ⊆ L_{t-1}`, and symmetrically (the mirror image used for (3.1))
`V \ L_{t-1} ⊆ R_{t-1}`. -/
theorem compl_R_subset_L (Γ d p t : ℕ) (ht0 : 0 < t) (ht : (t : ℝ) < ((d : ℝ) ^ p - 1) / 2) :
(R Γ d p (t - 1))ᶜ ⊆ L Γ d p (t - 1) ∧ (L Γ d p (t - 1))ᶜ ⊆ R Γ d p (t - 1) := 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. 1250, proof of Lemma 3.4, second paragraph ("for any t < (d^p − 1)/2, V \ R_{t−1} ⊆ L_{t−1}")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.