Methods for proving deterministic communication complexity lower bounds

Question

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?

Answer 1

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.

Answer 2

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.