Newman's theorem

Public coins can replace private coins, and Newman's theorem bounds the converse: private coins cost only a few more bits than public coins on finite inputs [New91], Kushilevitz and Nisan, Chapter 3. Let a public-coin protocol μ solve R on A × B with error ε, sending at most c bits. Draw 2 ^ k protocols from μ independently. On each pair of inputs the fraction of them that err is, by Hoeffding's inequality (Cslib.Probability.PMF.pi_sum_ge_mean_add), at least ε + δ with probability at most exp (-2 δ² 2 ^ k). If |X| |Y| exp (-2 δ² 2 ^ k) < 1, a union bound over the inputs leaves some choice of 2 ^ k protocols in which, on every pair of inputs, fewer than a fraction ε + δ err. Alice then picks one of them with k private random bits, sends her choice, and both run it: a private-coin protocol with error ε + δ sending at most k + c bits (PublicCoin.Solves.exists_privateCoin, PrivateCoin.ecomplexity_le_add).

For inputs of at most n bits, k = ⌈log₂ ⌈n / δ²⌉⌉ random bits suffice, that is O(log n + log (1 / δ)) extra bits (PrivateCoin.ecomplexity_le_add_clog).

Main results

• Cslib.Communication.PublicCoin.Solves.exists_privateCoin: the private-coin protocol.
• Cslib.Communication.PrivateCoin.ecomplexity_le_add: Newman's theorem for finite inputs.
• Cslib.Communication.PrivateCoin.ecomplexity_le_add_clog: Newman's theorem for inputs of n bits.

References

• I. Newman, Private vs. common random bits in communication complexity
• E. Kushilevitz and N. Nisan, Communication Complexity

theorem Cslib.Communication.PublicCoin.Solves.exists_privateCoin {X : Type u_1} {Y : Type u_2} {Z : Type u_3} {R : X → Y → Z → Prop} {A : Set X} {B : Set Y} [Finite X] [Finite Y] {μ : PublicCoin X Y Z} {ε δ : ℝ} {c k : ℕ} (hμ : μ.Solves ε R A B) (hc : μ.depth ≤ ↑c) (hδ : 0 ≤ δ) (hk : ↑(Nat.card X) * ↑(Nat.card Y) * Real.exp (-2 * δ ^ 2 * 2 ^ k) < 1) : ∃ (P : PrivateCoin k 0 X Y Z), P.Solves (ε + δ) R A B ∧ Protocol.depth P ≤ k + c

Newman's theorem, the construction. If a public-coin protocol solves R on A × B with error ε sending at most c bits, and |X| |Y| exp (-2 δ² 2 ^ k) < 1 for some δ ≥ 0, then a private-coin protocol in which Alice holds k random bits and Bob none solves R on A × B with error ε + δ sending at most k + c bits.

theorem Cslib.Communication.PrivateCoin.ecomplexity_le_add {X : Type u_1} {Y : Type u_2} {Z : Type u_3} {R : X → Y → Z → Prop} {A : Set X} {B : Set Y} [Finite X] [Finite Y] {ε δ : ℝ} (hδ : 0 ≤ δ) {k : ℕ} (hk : ↑(Nat.card X) * ↑(Nat.card Y) * Real.exp (-2 * δ ^ 2 * 2 ^ k) < 1) : ecomplexity (ε + δ) R A B ≤ PublicCoin.ecomplexity ε R A B + ↑k

Newman's theorem for finite inputs: if |X| |Y| exp (-2 δ² 2 ^ k) < 1 for some δ ≥ 0, private coins cost at most k more bits than public coins, for an extra error δ.

theorem Cslib.Communication.PrivateCoin.ecomplexity_le_add_clog {X : Type u_1} {Y : Type u_2} {Z : Type u_3} {R : X → Y → Z → Prop} {A : Set X} {B : Set Y} [Finite X] [Finite Y] {n : ℕ} (hX : Nat.card X ≤ 2 ^ n) (hY : Nat.card Y ≤ 2 ^ n) {ε δ : ℝ} (hδ : 0 < δ) : ecomplexity (ε + δ) R A B ≤ PublicCoin.ecomplexity ε R A B + ↑(Nat.clog 2 ⌈↑n / δ ^ 2⌉₊)

Newman's theorem for inputs of at most n bits: for δ > 0, private coins cost at most ⌈log₂ ⌈n / δ²⌉⌉ more bits than public coins, for an extra error δ.