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)} \lvert X \rvert \lvert Y \rvert\). Then, there are at least \(2^{g(n)}\)-monochromatic rectangles, so the lower bound is \(\Omega(\log_2 g(n))\).
To formally state the above intuition, we need to quantify the error. Let \(f: X\times Y \to O\) be a function and \(\mu\) be any probability distribution on \(X\times Y\). We define \(\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\in O\), we say that a subset \(S\subseteq I\) is called \(\epsilon\)-error \(z\)-monochromatic for \(f\) under \(\mu\) iff \(\mu(S) - \mu(S\cap f^{-1}(z)) \leq \epsilon \mu(S)\), i.e., \(\mu(S\cap f^{-1}(z)) \geq \alpha \cdot \mu(S)\) where \(I\) is the input set.
Let \(\epsilon'_{z\to z'}\) denote the total measure of inputs which the protocol answers \(z'\) while the correct answer is \(z\) (correct to wrong). By definition, the protocol answer \(z\) on \(\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 \(z\) must have at least \(\epsilon\) proportion of its total measure on which the correct answer is not \(z\). That is to say, for these \(b\) removing the correct answer that is \(z\), the wrong answer must be at least \(\epsilon\) a fraction of the remaining \(z\).
So, for all \(z\in O\), we have
\[\sum \epsilon'_{z'\to z} \geq \epsilon [\mu(f^{-1}(z)) + \sum \epsilon'_{z'\to z} - \sum \epsilon'_{z\to z'} - \alpha_z]\]
where \(\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 \(z\).
After rearranging, we have
\[\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\in O\), we have
\[\sum_{z\in O'} \alpha_z \geq \mu(f^{-1}(O')) - \epsilon'/\epsilon\]
where \(\epsilon' < \epsilon \cdot\mu(f^{-1}(O'))\), \(O'\subset O\).
Since there are at least \(\sum \alpha_z /\gamma\) rectangles, the lower bound is
\(\log_2( \mu(f^{-1}(O')) - \epsilon'/\epsilon)/\gamma)\).
This is the full theorem.
\(\textbf{Theorem} \text{(corruption bound)}\) Let \(\Gamma\) be the set of combinatorial rectangles on \(X\times Y\). Let \(f: X \times Y \to O, O'\subset O\). We use \(\mu\) to denote any probability distribution on \(X\times Y\), for \(\epsilon' < \epsilon \mu(f^{-1}(O'))\), we have
\[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.