3
$\begingroup$

I am familiar with the classic techniques for proving deterministic communication complexity lower bounds for boolean functions in the 2-party model: To the best of my knowledge, these are

  1. fooling sets,
  2. the rank method, and
  3. the "tiling method", which refers to determining the minimal number of monochromatic rectangles needed to cover all possible outputs.

It is known that (3) gives almost tight bounds but is difficult to apply. On the other hand, fooling sets are easier to find in general, but the obtained bounds can be exponentially smaller than the actual deterministic communication complexity, whereas the rank method yields lower bounds that can be polynomially smaller.

These are the only techniques that I am aware of and they were invented in the early 90s.

Are there any newer techniques for finding deterministic lower bounds?

Related question: Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?

$\endgroup$
  • 1
    $\begingroup$ w.r.t. (3) maybe you have in mind the partition number, which is stronger than the covering number (which corresponds to nondeterministic communication complexity). the partition bound can also be loose by a quadratic factor. how close to tight the rank lower bounds are is a famous open problem. $\endgroup$ – Sasho Nikolov Jun 10 '16 at 2:25
  • 1
    $\begingroup$ Information complexity is a more recent lower bound technique (for randomized communication) that may be useful to know as well? There's also nonnegative rank, which can be better than rank and is known to be quadratically related to deterministic communication complexity. There are also other relaxations of rank such as nondeterministic rank (or support rank) and approximate rank. $\endgroup$ – Robin Kothari Jun 10 '16 at 2:34
4
$\begingroup$

One approach that's quite different from the ones you mention is proving communication complexity lower bounds by reductions to query complexity problems. This approach can give lower bounds which are nearly quadratically stronger than the partition-based bounds, i.e. is able to actually exploit the structure of a deterministic communication protocol.

The basic idea is to compose a boolean function $f:\{0,1\}^k \to \{0,1\}$ with $k$ copies of a two party "gadget" function $g:\{0,1\}^{b} \times \{0,1\}^b \to \{0,1\}$, where $b = n/k$. It turns out that, by a simulation theorem of Raz and McKenzie, for a well-chosen $g$ and every $f$, the deterministic communication complexity of the composed function $F =f \circ g^k$ is equivalent up to lower-order factors to the deterministic decision tree complexity of $f$. The upshot is that to prove communication lower bounds it suffices to prove query lower bounds, which can be much easier.

See this paper by Göös, Pitassi, and Watson for references, and an application of this approach to giving nearly optimal separation between the partition number and deterministic communication complexity.

$\endgroup$
  • $\begingroup$ Thanks for the link! One question though: why is this method restricted to finding lower bounds that are "nearly quadratically stronger" than partition-based bounds? There are some examples where the deterministic communication complexity is $\Omega(n)$ whereas the non-deterministic and randomized case is $O(log n)$ such as the universal relation (Example 5.7 in KN). In general, do you see a problem with using this method for showing larger (than quadratic) separations for deterministic protocols? $\endgroup$ – miraculix101010 Jun 13 '16 at 10:16
  • $\begingroup$ What I meant is a quadratic separation between the logarithm of the partition number (=smallest number of monochromatic rectangles needed to partition the inputs) and deterministic communication complexity. The largest possible gap between these quantities is quadratic. The log of the partition number is not a lower bound on non-deterministic communication (where you allow covers rather than partitions) or on randomized communication (where rectangles do not have to be monochromatic). $\endgroup$ – Sasho Nikolov Jun 13 '16 at 11:49
  • $\begingroup$ I focused on deterministic communication because that's what you asked for. However, similar strategies -- prove a lower bound on decision tree complexity and transfer it to communication using a simulation theorem -- work for some randomized, quantum, and non-deterministic models as well. You need a different simulation theorem. $\endgroup$ – Sasho Nikolov Jun 13 '16 at 11:50
3
$\begingroup$

In addition to the ones you mentioned, a lower bound method in deterministic communication complexity that you can possibly add to your toolkit is norm based approaches as described in chapter 2, section 2.3 of this survey.

Here is a sample illustration of the method.

We define the trace norm of a $m\times n$ matrix $A$ as $$\|A\|_{tr}=\sum_{i=1}^{rank(A)}\lvert\sigma_i\rvert$$ where $\sigma_i$ is the $i$-th largest singular value of $A$.

For a function $f:X_1\times X_2\rightarrow \{-1,1\}$ that we want Alice and Bob to compute, where Alice receives some $x_1\in X_1$ and Bob receives $x_2\in X_2$, let the sign matrix representation of $f$, denoted $A_f$, be given by a $\lvert X_1\rvert \times\lvert X_2\rvert$ matrix where each row corresponds to some element of $X_1$ and each column corresponds to some element of $X_2$, with $f(x_1,x_2)$ in the entry where the row corresponding to $x_1$ intersects with the column corresponding to $x_2$.

We invoke a known result (theorem 18 in the linked survey) that $$D(f)\geq \log\mathrm{rank}(A)\geq \log\frac{\|A_f\|_{tr}^2}{\lvert X_1\rvert\lvert X_2\rvert}$$

When $X_1$ and $X_2$ are $\mathbb{F}_2^n$ and $f(x,y)=(-1)^{x\cdot y}$, where $x\cdot y$ is the inner product of $x$ and $y$, you can verify that $A_f$ is a Hadamard matrix$^1 $ with dimensions $2^n\times 2^n$.

The Hadamard matrix of dimension $2^n\times 2^n$ has $2^n$ singular values that are all equal to $2^{n/2}$. Using the lower bound given by the trace norm, and using the fact that $\lvert\mathbb{F}_2^n\rvert=2^n$ tells us that $D(f)$ is lower bounded by $$\log{\frac{(2^{3n/2})^2}{(2^n)^2}}=n$$

And indeed, one cannot do better than sharing their whole string to compute $f$.

There are many more involved arguments in proving lower bounds in deterministic communication complexity that rely on norms. It is also extends to the randomized setting.

Another useful technique you might consider picking up is discrepancy based approaches, although I have only seen this one used in proving lower bounds in randomized settings.

$^1$ A Hadamard matrix is one where all entries are $\pm 1$ and the rows are pairwise orthogonal.

$\endgroup$

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.