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?
Communication lower bounds for partial boolean functions
cc.complexity theory;lower bounds;communication complexity;boolean functions
(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.