Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma.

Abstract

Assume that we have an outer function $f:\{0, 1\}^n \to \{0, 1\}$ and a gadget function $g:A\times B \to\{0, 1\}$ and we want to lower bound deterministic communication complexity of a composed function $f\circ g^n$, denoted here by $D^{cc}(f\circ g^n)$, in terms of deterministic query complexity of $f$, denoted here by $D^{dt}(f)$. The study of such questions, now usually called \emph{Simulation Theorems}, was initiated in the work of Raz and McKenzie (\cite{raz1997separation}). Recently, Chattopadhyaay et al. (\cite{chattopadhyay2017simulation}) introduced a very convenient tool to study such questions, they called this tool \emph{hitting distributions}. Using this tool, they proved that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is either Inner Product or Gap Hamming Distance gadget on $k$ bits, and $f$ is any function depending on at most $2^{ck}$ variables for some absolute constant $c$. In this work we use hitting distributions to show Simulation Theorem for a new gadget. Our gadget is the following one: Alice holds $a\in \mathbb{F}_{p^2}$, Bob holds $b\in \mathbb{F}_{p^2}$ and they want to know whether $a - b$ is a square in $\mathbb{F}_{p^2}$. We show that $D^{cc}(f \circ g^n) = \Omega\left(D^{dt}(f) \cdot D^{cc}(g)\right)$, where $g$ is our gadget and $f$ is any function depending on at most $p^c$ variables for some constant $c$ (note that this bound is exponential in the size of gadget, which is $O(\log p)$). We also investigate hitting distributions for disjointness predicate on $k$-element subsets of $\{1, 2, \ldots, n\}$. Finally, we study Thickness Lemma, a combinatorial statement from the proof of Simulation Theorems of G\{o}\{o}s et al and Chattopadhyaay et al., and show that this Lemma can not be improved.