Toolbox

T1: The Corruption Method in Communication Complexity (2)

Reminder: This post contains 2691 words · 8 min read · by Xianbin

The ability of formalizing intuition is important. We already know the techniques of corruption bound. Basically, we need to show that the size of ϵ\epsilon-monochromatic rectangle can be larger than 2−g(n)∣X∣∣Y∣2^{-g(n)} \lvert X \rvert \lvert Y \rvert. Then, there are at least 2g(n)2^{g(n)}-monochromatic rectangles, so the lower bound is Ω(log⁡2g(n))\Omega(\log_2 g(n)).

To formally state the above intuition, we need to quantify the error. Let f:X×Y→Of: X\times Y \to O be a function and μ\mu be any probability distribution on X×YX\times Y. We define γ=max⁡{μ(S)∣S∈Γ is ϵ-error z-monochormatic}\textcolor{blue}{\gamma = \max \{\mu(S) \mid S \in \Gamma \text{ is } \epsilon\text{-error z-monochormatic}\}} where Γ\Gamma is a collection of subsets of the input set. For z∈Oz\in O, we say that a subset S⊆IS\subseteq I is called ϵ\epsilon-error zz-monochromatic for ff under μ\mu iff μ(S)−μ(S∩f−1(z))≤ϵμ(S)\mu(S) - \mu(S\cap f^{-1}(z)) \leq \epsilon \mu(S), i.e., μ(S∩f−1(z))≥α⋅μ(S)\mu(S\cap f^{-1}(z)) \geq \alpha \cdot \mu(S) where II is the input set.

Let ϵz→z′′\epsilon'_{z\to z'} denote the total measure of inputs which the protocol answers z′z' while the correct answer is zz (correct to wrong). By definition, the protocol answer zz on μ(f−1(z))+∑ϵz′→z′−∑ϵz→z′′\mu(f^{-1}(z))+\sum \epsilon'_{z'\to z} - \sum\epsilon'_{z\to z'} measure of the inputs.

By the definition of γ\gamma, any rectangle of measure larger than γ\gamma on which the protocol answers zz must have at least ϵ\epsilon proportion of its total measure on which the correct answer is not zz. That is to say, for these bb removing the correct answer that is zz, the wrong answer must be at least ϵ\epsilon a fraction of the remaining zz.

So, for all z∈Oz\in O, we have

∑ϵz′→z′≥ϵ[μ(f−1(z))+∑ϵz′→z′−∑ϵz→z′′−αz]\sum \epsilon'_{z'\to z} \geq \epsilon [\mu(f^{-1}(z)) + \sum \epsilon'_{z'\to z} - \sum \epsilon'_{z\to z'} - \alpha_z]

where αz=μ({x∣Π(x)=z,x∈⋃μ(R)≤γR})\alpha_z= \mu(\{x \mid \Pi(x) = z, x\in \bigcup_{\mu(R) \leq \gamma} R\}) is the total measure of the inputs in the rectangles of measure, at most γ\gamma on which the protocol outputs zz.

After rearranging, we have

αz≥μ(f−1(z))−∑ϵz→z′′−(1/ϵ−1)∑ϵz′→z′.\alpha_z \geq \mu(f^{-1}(z))-\sum \epsilon'_{z\to z'} - (1/\epsilon-1)\sum \epsilon'_{z'\to z}.

Summing over the choices of z∈Oz\in O, we have

∑z∈O′αz≥μ(f−1(O′))−ϵ′/ϵ\sum_{z\in O'} \alpha_z \geq \mu(f^{-1}(O')) - \epsilon'/\epsilon

where ϵ′<ϵ⋅μ(f−1(O′))\epsilon' < \epsilon \cdot\mu(f^{-1}(O')), O′⊂OO'\subset O.

Since there are at least ∑αz/γ\sum \alpha_z /\gamma rectangles, the lower bound is log⁡2(μ(f−1(O′))−ϵ′/ϵ)/γ)\log_2( \mu(f^{-1}(O')) - \epsilon'/\epsilon)/\gamma).

This is the full theorem.

Theorem(corruption bound)\textbf{Theorem} \text{(corruption bound)} Let Γ\Gamma be the set of combinatorial rectangles on X×YX\times Y. Let f:X×Y→O,O′⊂Of: X \times Y \to O, O'\subset O. We use μ\mu to denote any probability distribution on X×YX\times Y, for ϵ′<ϵμ(f−1(O′))\epsilon' < \epsilon \mu(f^{-1}(O')), we have

Rϵ′(f)≥Dϵ′μ(f)≥log⁡2(μ(f−1(O′))−ϵ′/ϵ)/γ).R_{\epsilon'}(f) \geq D_{\epsilon'}^\mu(f) \geq \log_2( \mu(f^{-1}(O')) - \epsilon'/\epsilon)/\gamma).

Reference

[1]. Beame, P., Pitassi, T., Segerlind, N. and Wigderson, A., 2006. A strong direct product theorem for corruption and the multiparty communication complexity of disjointness. computational complexity, 15, pp.391-432.