KRW Conjecture: separation of NC^1 and P

Question

More than a real question this is a recap of something I have been studying. I hope someone will help me getting things straight, so any correction or thought about the following reasoning is more than welcome. I am trying to get a grip on the KRW Conjecture, which is aimed at proving $NC^1 \neq P$.

What I figured out is that the main goal of the whole question is:

1. Find a boolean function $f$ such that $D(f) = \omega(\log(n))$, where $D(f)$ is the depth complexity of $f$ – the depth of the shallowest circuit computing $f$.

This would imply $NC^1 \neq P$ since it would prove the existence of a function $f$ which can be computed with a circuit of polynomial size but cannot be computed with a circuit of polylogarithmic depth:

2. $\exists\ f:\{0,1\}^n \rightarrow \{0,1\}\ |\quad f \in P/\mathrm{poly}$ and $f \notin NC^1$.

So we need tools to prove super-logarithmic lower bounds for boolean functions. To do so we can relate Circuit Complexity to Communication Complexity via the KW relations. Indeed it has been proved that every boolean function yields a KW relation defined as follows:

• Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean non-constant function.
• Alice receives $x \in f^{-1}(0)$.
• Bob receives $y \in f^{-1}(1)$.
• Their aim is to find $i$ such that $x_i \neq y_i$.

The reason why we want (and why it is possible) to relate circuits to KW relations is that it was proved what follows:

$D(f) = CC(KW_f)$, where $CC(KW_f)$ is the amount of bits communicated over a protocol solving $KW_f$.

Being communication problems, it is possible to prove lower bounds for KW relations using the Communication Complexity framework. The aim of Communication Complexity is to study the amount of communication, in terms of bits transmitted, required to solve a communication problem using a communication protocol, which is basically an algorithm stating the rules of the conversation.

For what it has been said until now we can establish a deep connection between circuits and protocols: Communication Complexity supplies a different point of view on the $NC^1 \neq P$ problem.

The first and most basic tool that comes from Communication Complexity are combinatorial rectangles:

A set $R \subseteq X \times Y$ is a (combinatorial) rectangle if $R = A \times B$ for $A \subseteq X$ and $B \subseteq Y$.

Furthermore, given a function $f: X \times Y\rightarrow Z$ and a rectangle $R \subseteq X \times Y$, $R$ is monochromatic in relation to $f$ if $f$ is constant over $R$.

Using rectangles it is possible to partition the space of input of any given function. Given a function $f$, the (base 2) logarithm of the amount of rectangles needed to cover the input space of $f$ gives a lower bound on the communication complexity of any protocol computing such $f$.

Here comes my first real question: given a function $f:X \times Y \rightarrow Z$, does proving that it is not possible to cover $X \times Y$ using at most n rectangles imply that $CC(f) = \omega(\log(n))$?

Now let’s talk about a practical example. The Equality Function is defined as follows: $$EQ(X,Y) =\begin{cases} 1&\text{if $X = Y$,}\\ 0&\text{otherwise.} \end{cases}$$

Since it can be proved using rectangles that $CC(EQ) = n + 1$, wouldn’t that mean that $D(EQ) = \omega(\log(n))$?

There’s something slipping my grasp, thanks in advance to everyone who will spend some of their time to reply.

Answer 1

There are a few points to consider here:

1. If we wish to show that $CC(f) = \omega(\log n)$, we should show that it is not possible to cover the domain of $f$ using $\mathrm{poly}(n)$ monochromatic rectangles (rather than $n$ rectangles). Showing it for $n$ rectangles would only establish that $CC(f) > \log n$.

2. If we wish to prove a lower bound on $D(EQ)$, then we should prove a lower bound on $CC(\mathit{KW}_{EQ})$ rather than on $CC(EQ)$. Therefore, the lower bound on $CC(EQ)$ does not imply a lower bound on $D(EQ)$.

3. In particular, in order to use the Karchmer-Wigderson approach to prove lower bounds on depth complexity, we need to prove lower bounds on the communication complexity of relations rather than functions. This is considerably trickier. For example, in the context of relations, one needs to change the definition of a monochromatic rectangle. Now, it no longer makes sense to require that "the function is constant over $f$" since a relation may allow multiple valid solutions for every input, so it is not clear what being "constant" means. Instead, one should use the following more complicated definition: a rectangle $R \subseteq X \times Y$is said to be monochromatic with respect to a relation $S \subseteq X \times Y \times Z$ if there exists an output $z\in Z$ that is a valid solution for every input in $R$ (i.e., $(x,y,z) \in S$ for every $(x,y) \in R$).

4. Alas, it is not possible to use rectangle covers to prove meaningful lower bounds on KW relations. The reason is that every KW relations can be covered by $2n$ rectangles. Those rectangles are constructed as follows: for every index $i \in [n]$ and bit $b \in \{0,1\}$ we have the rectangle $$R_{i,b} = \{ x\in f^{-1}(0) \mid x_i = b \} \times \{ y\in f^{-1}(1) \mid y_i = \neg b \}. $$ It is not hard to see that those rectangles are indeed monochromatic rectangles for any KW relation $\mathit{KW}_f$, and that they cover the whole domain of the KW relation.