Communication lower bounds for partial boolean functions

Question

There are well known techniques for proving lower bounds on the communication complexity of boolean functions, like fooling sets, the rank of the communication matrix, and discepancy.

1) How do we use these techniques for lower bounding partial boolean functions? More specifically, how do you count the rectangles in the communication matrix? Do you also count the "undefined part" of the function? Or do you leave it out?

Another thing, what are the known relations between the communication complexity of total and partial functions? For example, is there a function $f$ with a promise version of it, call it $f'$, such that $C(f)\neq C(f')$? (here $C$ could be any communication complexity measure like deterministic, probabilistic with all its flavors, quantum). A concrete example is the equality function EQ, and its promise version defined in this paper denoted as EQ'. It is known that $C(EQ)=n$ and $C(EQ')=\Omega(n)$ where $C$ is the bounded error communication complexity (see the paper). There is no matching upper bound here, but they are asymptotically the same.

2) Is there a function defined in the same spirit of EQ and EQ', but with a different complexity?

Answer 1

(1) The way I like to think about partial functions is by defining a total function with three outputs e.g, $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1, *\}$. The $*$ values are where your partial function is undefined.

(2) You can still define a "monochromatic" rectangle in this case. But here, you allow $*$'s to be in the rectangle.

A rectangle $R$ is monochromatic if $f(R) \subseteq \{0,*\}$ or $f(R) \subseteq \{1,*\}$.

From this, you can still use many of the standard lower bounds techniques such as fooling sets.

(3) As Marc mentions, you can always define trivial partial functions where the communication complexity is much less than the original. For example, say the partial function TEQ is the EQ function, restricted to $(x,y)$ pairs such that $x \neq y$.

A partial function that people might care about is the Gap-Hamming-Distance function. $GHD_{n,g}$ is takes two $n$ bit strings $x,y$ and returns $1$ if their Hamming distance is more than $n/2 + g$ and returns $0$ if their Hamming distance is less than $n/2 - g$. (The Hamming distance $\Delta(x,y)$ is the number of $i$ where $x_i \neq y_i$.)

People are really particularly interested in the randomized communication complexity of $GHD$. It's not hard to show that the gapless version (Alice/Bob want to tell if $\Delta(x,y)$ is greater than $n/2$ or not) requires $\Omega(n)$ bits of communication.

It turns out that when $g = O(\sqrt{n})$, you still need a linear amount of communication. However, when $g = \omega(\sqrt{n})$, you can get away with only $O((n/g)^2)$ bits. When $g = \Omega(n)$, you get a partial function with $O(1)$ communication complexity.

The $g = \Theta(\sqrt{n})$ case seems to be the "important case". Indyk and Woodruff introduced this problem, gave a lower bound for one-way randomized protocols, and used it to get lower bounds for streaming algorithms that estimate frequency moments. The state of the art lower bound is $\Omega(n)$ bits for any randomized protocol and is due to Chakrabarti and Regev.

Piotr Indyk and David Woodruff. Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003.

Amit Chakrabarti and Oded Regev. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. http://arxiv.org/pdf/1009.3460.

Answer 2

The fundamental fact on which relies all the lower bound methods that you give is that a $t$-bit communication protocol partitions the input set into at most $2^t$ monochromatic rectangles. More precisely, the set of inputs corresponding to a given transcript $\sigma$ (and therefore a given output) is a product set $S \times T$. A key observation is that this is a property of communication protocols, which holds both for total or partial functions. Certainly, your partition does not need to cover the parts where the function is undefined. On the other hand, if the protocol is designed in such a way that it answers something for some undefined value, it still computes the function correctly.

This leads to defining the partition number of a partial function as the minimum number of disjoint rectangles required to cover the domain of the function. Each rectangle have to agree with the value of the function on its domain, but can have arbitrary values outside. By the previous argument, the logarithm of the partition number is a lower bound on the communication complexity of (partial) functions. From this lower bound, you can derive all the others.