Newman's Theorem: Public Coin to Private Coin Reduction

A public-coin protocol can be simulated by a private-coin protocol with only O(log(|X|·|Y|)) additional random bits, at the cost of slightly increasing the error.

Direct conversion

The simplest conversion from public-coin to private-coin: Alice has n private coin bits, sends them all to Bob as a single CoinTape n-valued message (costing n bits), then both deterministically simulate the public-coin protocol.

Newman's theorem

By Chernoff + union bound, only O(log(|X|·|Y|)/ε²) random seeds are needed, giving a much cheaper conversion.

noncomputable instance CommunicationComplexity.Unit.measureSpace : MeasureTheory.MeasureSpace Unit

Unit with the Dirac probability measure.

Equations

• CommunicationComplexity.Unit.measureSpace = { toMeasurableSpace := PUnit.instMeasurableSpace, volume := MeasureTheory.Measure.dirac () }

instance CommunicationComplexity.Unit.isProbabilityMeasure : MeasureTheory.IsProbabilityMeasure MeasureTheory.volume

noncomputable instance CommunicationComplexity.Unit.finiteProbabilitySpace : FiniteProbabilitySpace Unit

Equations

• CommunicationComplexity.Unit.finiteProbabilitySpace = CommunicationComplexity.FiniteProbabilitySpace.of Unit

@[reducible, inline]

noncomputable abbrev CommunicationComplexity.PublicCoin.newmanIndexSpace (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : Type

The number of random seeds Alice samples from in the Newman reduction: Fin (derandomizationSamples X Y ε c).

Equations

• CommunicationComplexity.PublicCoin.newmanIndexSpace X Y ε c = Fin (CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples X Y ε c)

noncomputable instance CommunicationComplexity.PublicCoin.newmanIndexSpace.fintype (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : Fintype (newmanIndexSpace X Y ε c)

Equations

• CommunicationComplexity.PublicCoin.newmanIndexSpace.fintype X Y ε c = inferInstance

instance CommunicationComplexity.PublicCoin.newmanIndexSpace.nonempty (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : Nonempty (newmanIndexSpace X Y ε c)

noncomputable instance CommunicationComplexity.PublicCoin.newmanIndexSpace.measureSpace (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : MeasureTheory.MeasureSpace (newmanIndexSpace X Y ε c)

Equations

• One or more equations did not get rendered due to their size.

instance CommunicationComplexity.PublicCoin.newmanIndexSpace.isProbabilityMeasure (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : MeasureTheory.IsProbabilityMeasure MeasureTheory.volume

noncomputable instance CommunicationComplexity.PublicCoin.newmanIndexSpace.finiteProbabilitySpace (X : Type u_1) (Y : Type u_2) [Fintype X] [Fintype Y] (ε c : ℝ) : FiniteProbabilitySpace (newmanIndexSpace X Y ε c)

Equations

• CommunicationComplexity.PublicCoin.newmanIndexSpace.finiteProbabilitySpace X Y ε c = CommunicationComplexity.FiniteProbabilitySpace.of (CommunicationComplexity.PublicCoin.newmanIndexSpace X Y ε c)

noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol {Ω : Type u_1} {X : Type u_2} {Y : Type u_3} {α : Type u_4} [FiniteProbabilitySpace Ω] [Fintype X] [Fintype Y] (p : Protocol Ω X Y α) (f : X → Y → α) (ε c : ℝ) (hc : 1 < c) (hp : p.ApproxComputes f ε) : PrivateCoin.FiniteMessage.Protocol (newmanIndexSpace X Y ε c) Unit X Y α

The Newman reduction: given a public-coin protocol that ε-computes f, construct a private-coin protocol where Alice samples a random index i from newmanIndexSpace and sends it to Bob. Both then simulate the public-coin protocol with the i-th seed from a fixed table of good randomness values (chosen via Chernoff + union bound).

Equations

• One or more equations did not get rendered due to their size.

theorem CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_ApproxComputes {Ω : Type u_1} {X : Type u_2} {Y : Type u_3} {α : Type u_4} [FiniteProbabilitySpace Ω] [Fintype X] [Fintype Y] (p : Protocol Ω X Y α) (f : X → Y → α) (ε c : ℝ) (hc : 1 < c) (hp : p.ApproxComputes f ε) : (p.newmanProtocol f ε c hc hp).ApproxComputes f (c * ε)

theorem CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexity {Ω : Type u_1} {X : Type u_2} {Y : Type u_3} {α : Type u_4} [FiniteProbabilitySpace Ω] [Fintype X] [Fintype Y] (p : Protocol Ω X Y α) (f : X → Y → α) (ε c : ℝ) (hc : 1 < c) (hp : p.ApproxComputes f ε) : Deterministic.FiniteMessage.Protocol.complexity (p.newmanProtocol f ε c hc hp) = Nat.clog 2 (derandomizationSamples X Y ε c) + Deterministic.FiniteMessage.Protocol.complexity p

theorem CommunicationComplexity.PublicCoin.newman {X : Type u_1} {Y : Type u_2} {α : Type u_3} [Fintype X] [Fintype Y] (f : X → Y → α) (ε ε' c : ℝ) (hc : 1 < c) (hε' : c * ε < ε') : PrivateCoin.communicationComplexity f ε' ≤ communicationComplexity f ε + ↑(Nat.clog 2 (FiniteMessage.Protocol.derandomizationSamples X Y ε c))

Newman's theorem: for any ε' > c·ε, private-coin communication complexity at error ε' is at most public-coin complexity at error ε plus O(log(|X|·|Y|)/ε²) bits.