19
$\begingroup$

Background:

Consider the usual two-party model of communication complexity where Alice and Bob are given $n$-bit strings $x$ and $y$ and have to compute some Boolean function $f(x,y)$, where $f:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$.

We define the following quantities:

$D(f)$ (the deterministic communication complexity of $f$): The minimum number of bits that Alice and Bob need to communicate to compute $f(x,y)$ deterministically.

$Pn(f)$ (the partition number of $f$): The logarithm (base 2) of the smallest number of monochromatic rectangles in a partition (or a disjoint cover) of $\{0,1\}^n \times \{0,1\}^n$.

A monochromatic rectangle in $\{0,1\}^n \times \{0,1\}^n$ is a subset $R \times C$ such that $f$ takes the same value (i.e., is monochromatic) on all elements of $R \times C$.

Also note that the partition number is different from the "protocol partition number", which was the subject of this question.

See the text by Kushilevitz and Nisan for more information. In their notation, what I have defined to be $Pn(f)$ is $\log_2 C^D(f)$.

Note: These definitions are easily generalized to non-Boolean functions $f$, where the output of $f$ is some larger set.


Known results:

It is known that $Pn(f)$ is a lower bound on $D(f)$, i.e., for all (Boolean or non-Boolean) $f$, $Pn(f) \leq D(f)$. Indeed, most lower bound techniques (or perhaps all?) for $D(f)$ actually lower bound $Pn(f)$. (Can anyone confirm that this is true of all lower bound techniques?)

It is also known that this bound is at most quadratically loose (for Boolean or non-Boolean functions), i.e., $D(f) \leq (Pn(f))^2$. To summarize, we know the following:

$Pn(f) \leq D(f) \leq (Pn(f))^2$

It is conjectured that $Pn(f) = \Theta(D(f))$. (This is open problem 2.10 in the text by text by Kushilevitz and Nisan.) However, to the best of my knowledge, the best known separation between these two for Boolean functions is only by a multiplicative factor of 2, as shown in "The Linear-Array Conjecture in Communication Complexity Is False" by Eyal Kushilevitz, Nathan Linial, and Rafail Ostrovsky.

More precisely, they exhibit an infinite family of Boolean functions $f$, such that $D(f) \geq (2 - o(1)) Pn(f)$.


Question:

What is the best known separation between $Pn(f)$ and $D(f)$ for non-Boolean functions? Is it still the factor-2 separation referenced above?

Added in v2: Since I haven't received an answer in a week, I'm also happy to hear partial answers, conjectures, hearsay, anecdotal evidence, etc.

$\endgroup$
  • $\begingroup$ Are you sure about $D(f) \le (Pn(f))^2$? Lemma 3.8 in Jukna's book only proves $D(f) \le 2(Pn(f))^2$, and KN only state $D(f) = O((Pn(f))^2)$. $\endgroup$ – András Salamon Mar 26 '14 at 16:07
  • 1
    $\begingroup$ @AndrásSalamon: I wasn't too careful stating the upper bound since I'm looking for functions closer to the lower bound, but I think $(Pn(f)+1)^2$ is achievable. See Theorem 2.2 in "Lower Bounds in Communication Complexity" by Troy Lee and Adi Shraibman. $\endgroup$ – Robin Kothari Mar 26 '14 at 21:47
  • $\begingroup$ Since $Pn(f) \le \log L(f) \le D(f)$, where $L(f)$ is the smallest number of leaves in a communication protocol tree for $f$, it may be possible to come up with a lower bound for $\log L(f)$ that is not technically a lower bound for $Pn(f)$. However, since $D(f) \le 3.4\,\log L(f)$, such a lower bound would essentially establish a close approximation to the precise value of $D(f)$. $\endgroup$ – András Salamon Apr 2 '14 at 12:25
  • $\begingroup$ See also the related answer cstheory.stackexchange.com/a/3352/109 $\endgroup$ – András Salamon Apr 3 '14 at 1:57
8
$\begingroup$

This question has just been resolved! As I mentioned, it was known that

$Pn(f) \leq D(f) \leq (Pn(f))^2$,

but it was a major open problem to show that either $Pn(f) = \Theta(D(f))$ or that there exists a function for which $Pn(f) = o(D(f))$.

A few days ago this was resolved by Mika Göös, Toniann Pitassi, Thomas Watson (http://eccc.hpi-web.de/report/2015/050/). They show that there exists a function $f$ which satisfies

$Pn(f) = \tilde{O}((D(f))^{2/3})$.

They also show an optimal result for the one-sided version of $Pn(f)$, which I'll denote by $Pn_1(f)$, where you only need to cover the 1-inputs with rectangles. $Pn_1(f)$ also satisfies

$Pn_1(f) \leq D(f) \leq (Pn_1(f))^2$,

and they show that this is the best possible relation between the two measures, since they exhibit a function $f$ which satisfies

$Pn_1(f) = \tilde{O}((D(f))^{1/2})$.

$\endgroup$
  • $\begingroup$ This nicely wraps up the question! $\endgroup$ – András Salamon Apr 11 '15 at 14:31
7
$\begingroup$

You remark that lower bounds on $Pn(f)$ are closely related to all existing lower bound techniques. For Boolean functions this seems to be true, as long as the log-rank conjecture is true. However, $Pn(f)$ can be exponentially larger than the fooling set bound.

It is not clear to me how much $Pn(f)$ and $D(f)$ can differ in the non-Boolean case.

In the remainder I make these comments more precise.


KN (Kushilevitz and Nisan in their 1997 textbook) outline the three basic techniques for Boolean functions: size of a fooling set, size of a monochromatic rectangle, and rank of the communication matrix.

First, fooling sets. A fooling set $S$ is monochromatic: there is some $z \in \{0,1\}$ such that $f(x,y) = z$ for every $(x,y)\in S$. Some final patching is then needed to take into account the other colour. This extra step can be avoided. Let $f \colon X \times Y \to \{0,1\}$ be a function. A pair of distinct elements $(x_1,y_1),(x_2,y_2) \in X \times Y$ is weakly fooling for $f$ if $f(x_1,y_1) = f(x_2,y_2)$ implies that either $f(x_1,y_2) \ne f(x_1,y_1)$ or $f(x_2,y_1) \ne f(x_1,y_1)$. A set $S \subseteq X \times Y$ is a weak fooling set for $f$ if every distinct pair of elements of $S$ is weakly fooling. KN implicitly state after the proof of 1.20 that the log-size of a weak fooling set is a lower bound for the communication complexity.

A largest weak fooling set picks a representative element from each monochromatic rectangle in a smallest disjoint set cover. The size of a largest weak fooling set is therefore at most as large as (the exponent of) the partition number. Unfortunately the bound provided by fooling sets is often weak. The proof of KN 1.20 shows that any function mapping each element $s$ of a weak fooling set $S$ to a monochromatic rectangle $R_s$ containing that element is injective. However, there can be many monochromatic rectangles $R$ in a smallest disjoint cover that do not appear in the image of $S$, with every element of $R$ weakly fooling with some but not all of the elements of $S$, and so cannot simply be added to $S$. In fact Dietzfelbinger, Hromkovič and Schnitger showed (doi:10.1016/S0304-3975(96)00062-X) that for all large enough $n$, at least $1/4$ of all Boolean functions on $n$ variables have $Pn(f) = n$ yet have (weak) fooling sets of log-size $O(\log n)$. So the log of the size of a largest (weak) fooling set can be exponentially smaller than the communication complexity.

For rank, establishing a close correspondence between the rank of the matrix of the function and its partition number would establish a form of the log-rank conjecture (depending on the tightness of the correspondence). For instance, if there is a constant $a> 0$ such that $Pn(f) \le a\log rk(f)$ for every Boolean function $f$, then $D(f) \le (2a\log rk(f))^2$, and a kind of log-rank conjecture then holds for families of functions for which $rk(f)$ ultimately increases with $|X|+|Y|$, with exponent $2+\epsilon$ for any $\epsilon > 0$ achievable for sufficiently large $|X|+|Y|$. (Recall that the Lovász-Saks log-rank conjecture says that there is a constant $c>0$ such that $D(f) \le (\log rk(f))^c$ for every Boolean function $f$; here $rk(f)$ is the rank of the communication matrix of $f$ over the reals.)

Similarly, if there is only one quite large monochromatic rectangle together with many small ones, then the partition number gives a stronger bound than the log-size of a largest monochromatic rectangle. However, the log-rank conjecture is also equivalent to a conjecture about the size of a largest monochromatic rectangle (Nisan and Wigderson 1995, doi:10.1007/BF01192527, Theorem 2). So using monochromatic rectangles is not currently known to be "the same as" using the partition number, but they are closely related if the log-rank conjecture holds.

In summary, the log-size of a largest weak fooling set may be exponentially smaller than the partition number. There may be gaps between the other lower bound techniques and the partition number, but if the log-rank conjecture holds then these gaps are small.

By using notions of size that extend the usual one (of cardinality), the size of any monochromatic rectangle can be used to generalise fooling sets, and to lower bound the communication complexity (see KN 1.24). I am not sure how close the generalised largest "size" of any monochromatic rectangle must be to the communication complexity.

In contrast to the above discussion for Boolean functions, for non-Boolean functions the gap between $D(f)$ and $\log rk(f)$ may be exponential. KN 2.23 gives an example: let $f$ be the function that returns the size of the intersections of the sets represented by the two input characteristic vectors. For this function, the log-rank is $\log n$. Now the set of all pairs of non-intersecting sets has $3^n$ elements. As far as I can tell, there can be no monochromatic rectangles larger than this set. If this is correct, then $D(f) \ge Pn(f) \ge (2 - \log 3)n > 0.4n$, so for this function, $D(f)$, $Pn(f)$, and the log-size of a largest monochromatic rectangle are all within a factor of at most $2.5$ of each other, while being exponentially far from the log rank. Hence small separations between $Pn(f)$ and $D(f)$ may be possible in the non-Boolean case, but they are not related in an obvious way to the log-rank of the matrix of $f$. I am not aware of any published work discussing how these measures are related in the non-Boolean case.

Finally, Dietzfelbinger et al. also defined an extended fooling set bound, generalising the fooling condition from pairs ("order 1" subsets) to larger subsets of monochromatic elements; the extended fooling condition requires that the submatrix spanned by the monochromatic elements is not monochromatic. It is not clear how this behaves as the order of the monochromatic subsets increases, as one has to divide the size of the extended fooling set by the order, and consider the largest value over all orders. However, this notion ends up being a close lower bound to $Pn(f)$.

$\endgroup$
  • $\begingroup$ Thanks for sharing your observations. About the first statement, I think the fact that $Pn(f)$ is related to all lower bound techniques for $D(f)$ is true independent of the log rank conjecture. As far as I know, every lower bound technique for $D(f)$ is actually a lower bound technique for $Pn(f)$, including the log rank lower bound. $\endgroup$ – Robin Kothari Mar 28 '14 at 14:06
  • $\begingroup$ @Robin: Apologies for my lack of clarity; the key phrases are "closely related" and "how much... can differ". I am taking as given the known inequalities such as $D(f) \ge Pn(f) \ge 2n - \log mono(f)$, where $mono(f)$ is the number of entries in a largest monochromatic rectangle in the matrix of $f$, and the domain of $f$ is $2^n\times 2^n$. My comment is about how close these inequalities are, for instance whether they avoid exponential gaps, and why the weak fooling set size is more useful than the usual notion (the monochromatic version can be exponentially smaller than the rank bound). $\endgroup$ – András Salamon Mar 30 '14 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.