<p>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.</p>

<p>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 <em>every</em> $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.</p>

<p>See this <a href="http://eccc.hpi-web.de/report/2015/050/" rel="nofollow">paper by Göös, Pitassi, and Watson</a> for references, and an application of this approach to giving nearly optimal separation between the partition number and deterministic communication complexity.</p>

CC BY-SA 3.0
2016-06-13T10:16:09.660Z
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?
miraculix101010
CC BY-SA 3.0
2016-06-13T11:49:14.640Z
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).
Sasho Nikolov
CC BY-SA 3.0
2016-06-13T11:50:37.610Z
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.
Sasho Nikolov
CC BY-SA 3.0
2016-06-10T02:53:56.977Z
2016-06-10T02:53:56.977Z
Sasho Nikolov
<p>In addition to the ones you mentioned, a lower bound method in deterministic communication complexity that you can possibly add to your toolkit is <strong>norm based approaches</strong> as described in chapter 2, section 2.3 of <a href="http://www.research.rutgers.edu/~troyjlee/survey_plain.pdf" rel="nofollow">this survey</a>.</p>

<p>Here is a sample illustration of the method.</p>

<p>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$.</p>

<p>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$.</p>

<p>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}$$</p>

<p>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$.</p>

<p>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$$</p>

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

<p>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.</p>

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

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

CC BY-SA 3.0
2016-06-10T01:59:54.040Z
2016-06-10T01:59:54.040Z
Sidhanth Mohanty
<p>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 </p>

<ol>
<li><em>fooling sets</em>, </li>
<li>the <em>rank method</em>, and </li>
<li>the "tiling method", which refers to determining the minimal number of monochromatic rectangles needed to cover all possible outputs. </li>
</ol>

<p>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.</p>

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

<p><strong>Are there any newer techniques for finding deterministic lower bounds?</strong> </p>

<p>Related question: 
<a href="https://cstheory.stackexchange.com/questions/30548/is-it-possible-to-prove-stronger-bounds-for-the-deterministic-communication-comp">Is it possible to prove stronger bounds for the deterministic communication complexity compared to nondeterministic communication complexity?</a></p>

CC BY-SA 3.0
2016-06-10T02:25:13.993Z
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.
Sasho Nikolov
CC BY-SA 3.0
2016-06-10T02:34:24.793Z
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.
Robin Kothari
<communication-complexity>
Methods for proving deterministic communication complexity lower bounds
miraculix101010
# Methods for proving deterministic communication complexity lower bounds

(Asked by: username_0 on 2016-06-10)

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?](https://cstheory.stackexchange.com/questions/30548/is-it-possible-to-prove-stronger-bounds-for-the-deterministic-communication-comp)

**Tags:** communication-complexity
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 2 answers

### Answer by username_1 on 2016-06-10. Score: 4

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](http://eccc.hpi-web.de/report/2015/050/) for references, and an application of this approach to giving nearly optimal separation between the partition number and deterministic communication complexity.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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).  
> **username_1**: 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.  

---

### Answer by username_3 on 2016-06-10. Score: 3

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](http://www.research.rutgers.edu/~troyjlee/survey_plain.pdf).

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.


---

