Heterogeneous communication complexity
DefinitionSparseHistComm_Supplement_Chetcommunication-complexitydistributed-estimationhistogram-aggregationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For users, -sparse binary inputs in dimension , distortion , and failure probability , the heterogeneous communication complexity is
The infimum ranges over every protocol in the paper's heterogeneous model: users may use different encoders, messages are arbitrary finite binary strings, and public and private randomness are allowed.
Formalization Note The value lies in . This is exactly the published homogeneous complexity with only the common-encoder condition removed; no prefix-free or bounded-length condition is added.
Definition code
import Mathlib import Definitions.Def_SparseHistComm_worstCost import Definitions.Def_SparseHistComm_IsAccurate open scoped ENNReal namespace SparseHistComm namespace Supplement /-- `C_het(D, δ)`, the infimum of the worst-case expected communication cost over all accurate heterogeneous protocols (Ye–Fan, *Optimal Communication for Distributed Sparse Histogram Aggregation*, arXiv:2611.04285 (held version, sha256 29df82a4…f27c6f), Section I, p.3, and Theorem 2, p.9). **Formalization Note** This differs from the published `SparseHistComm.Chom` only by omitting `IsHomogeneous`: the infimum ranges over every published `Protocol n d`, with arbitrary public randomness, per-user channels into `List Bool`, and measurable decoder. No prefix-free or bounded message-length condition is imposed. -/ noncomputable def Chet (n k d : ℕ) (D δ : ℝ) : ℝ≥0∞ := ⨅ (P : Protocol n d) (_ : IsAccurate P k D δ), worstCost P k end Supplement end SparseHistComm
Source
Ye–Fan, Optimal Communication for Distributed Sparse Histogram Aggregation, arXiv:2611.04285 (held version, sha256 29df82a4…f27c6f), Section I, p.3, and Theorem 2, p.9