Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-019 | 17th February 2022 04:10

Simulation Methods in Communication Lower Bounds, Revisited


Authors: Guangxu Yang, Jiapeng Zhang
Publication: 17th February 2022 11:45
Downloads: 257


The notion of lifting theorems is a generic method to lift hardness of one-party functions to two-party lower bounds in communication model. It has many applications in different areas such as proof complexity, game theory, combinatorial optimization. Among many lifting results, a central idea is called Raz-McKenize simulation (FOCS 1997). This simulation provides a systematic way to convert a communication protocol into a corresponding decision tree. Though it is very convenient in many applications, there are still some challenges in this framework. A major problem is that Raz-McKenize simulation requires a very large gadget.

In this paper, we revise Raz-McKenzie simulation. We introduce a white-box simulation, proving lifting theorems for block sensitivity with constant-size gadgets. Concretely, we show there is a constant-size gadget $g$ such that for any Boolean function $f$, the corruption bound of $f\circ g^n$ is lower bounded by $\Omega(\mathrm{bs}(f))$. Combined with a result of Beame et al. (CCC 2005), this implies the randomized communication complexity of $f\circ g^n$ is lower bounded by $\Omega(\mathrm{bs}(f))$. Besides the result itself, we believe our simulation technique may have more applications in diverse areas. We also discuss why our simulation method has a potential to avoid the large-size gadget bottleneck in Raz-McKenzie simulation.

ISSN 1433-8092 | Imprint