TR22-019 Authors: Guangxu Yang, Jiapeng Zhang

Publication: 17th February 2022 11:45

Downloads: 257

Keywords:

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.