<p>There are a few points to consider here:</p>
<ol>
<li><p>If we wish to show that <span class="math-container">$CC(f) = \omega(\log n)$</span>, we should show that it is not possible to cover the domain of <span class="math-container">$f$</span> using <span class="math-container">$\mathrm{poly}(n)$</span> monochromatic rectangles (rather than <span class="math-container">$n$</span> rectangles). Showing it for <span class="math-container">$n$</span> rectangles would only establish that <span class="math-container">$CC(f) &gt; \log n$</span>.</p>
</li>
<li><p>If we wish to prove a lower bound on <span class="math-container">$D(EQ)$</span>, then we should prove a lower bound on <span class="math-container">$CC(\mathit{KW}_{EQ})$</span> rather than on <span class="math-container">$CC(EQ)$</span>. Therefore, the lower bound on <span class="math-container">$CC(EQ)$</span> does not imply a lower bound on <span class="math-container">$D(EQ)$</span>.</p>
</li>
<li><p>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 <em>relations</em> 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 &quot;the function is constant over <span class="math-container">$f$</span>&quot; since a relation may allow multiple valid solutions for every input, so it is not clear what being &quot;constant&quot; means. Instead, one should use the following more complicated definition: a rectangle <span class="math-container">$R \subseteq X \times Y$</span>is said to be <em>monochromatic</em> with respect to a relation <span class="math-container">$S \subseteq X \times Y \times Z$</span> if there exists an output <span class="math-container">$z\in Z$</span> that is a valid solution for every input in <span class="math-container">$R$</span> (i.e., <span class="math-container">$(x,y,z) \in S$</span> for every <span class="math-container">$(x,y) \in R$</span>).</p>
</li>
<li><p>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 <span class="math-container">$2n$</span> rectangles. Those rectangles are constructed as follows: for every index <span class="math-container">$i \in [n]$</span> and bit <span class="math-container">$b \in \{0,1\}$</span> we have the rectangle <span class="math-container">$$R_{i,b} = \{ x\in f^{-1}(0) \mid x_i = b \} \times \{ y\in f^{-1}(1) \mid y_i = \neg b \}. $$</span> It is not hard to see that those rectangles are indeed monochromatic rectangles for any KW relation <span class="math-container">$\mathit{KW}_f$</span>, and that they cover the whole domain of the KW relation.</p>
</li>
</ol>

CC BY-SA 4.0
2021-04-11T22:09:01.807Z
Thank you for the exhaustive answer. Of course it is to be proved the lower bound on CC(KWeq) rather than CC(EQ); it was pretty silly of me not to notice it, thanks again for the clear explanation. I have never taken into accounts the changes in the definitions of monochromatic rectangles when talking about relations rather than functions. If I am not getting it wrong, those changes imply monochromatic rectangles being useless with the Karchmer-Wigderson approach. Since every KW relation can be covered using 2n monochromatic rectangles, it would hold CC(KW) >= log 2n for every KW relation.
Pietro D'Amico
CC BY-SA 4.0
2021-04-11T22:39:19.837Z
Yes, this is exactly what I meant.
Or Meir
CC BY-SA 4.0
2021-04-10T22:30:07.520Z
2021-04-10T22:30:07.520Z
Or Meir
<p>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 <span class="math-container">$NC^1 \neq P$</span>.</p>
<p>What I figured out is that the main goal of the whole question is:</p>
<blockquote>
<ol>
<li>Find a boolean function <span class="math-container">$f$</span> such that <span class="math-container">$D(f) = \omega(\log(n))$</span>, where <span class="math-container">$D(f)$</span> is the depth complexity of <span class="math-container">$f$</span> – the depth of the shallowest circuit computing <span class="math-container">$f$</span>.</li>
</ol>
</blockquote>
<p>This would imply  <span class="math-container">$NC^1 \neq P$</span> since it would prove the existence of a function <span class="math-container">$f$</span> which can be computed with a circuit of polynomial size but cannot be computed with a circuit of polylogarithmic depth:</p>
<blockquote>
<ol start="2">
<li><span class="math-container">$\exists\ f:\{0,1\}^n \rightarrow \{0,1\}\ |\quad f \in P/\mathrm{poly}$</span> and <span class="math-container">$f \notin NC^1$</span>.</li>
</ol>
</blockquote>
<p>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:</p>
<blockquote>
<ul>
<li>Let <span class="math-container">$f:\{0,1\}^n \rightarrow \{0,1\}$</span> be a boolean non-constant function.</li>
<li>Alice receives <span class="math-container">$x \in f^{-1}(0)$</span>.</li>
<li>Bob receives <span class="math-container">$y \in f^{-1}(1)$</span>.</li>
<li>Their aim is to find <span class="math-container">$i$</span> such that <span class="math-container">$x_i \neq y_i$</span>.</li>
</ul>
</blockquote>
<p>The reason why we want (and why it is possible) to relate circuits to KW relations is that it was proved what follows:</p>
<blockquote>
<p><span class="math-container">$D(f) = CC(KW_f)$</span>, where <span class="math-container">$CC(KW_f)$</span> is the amount of bits communicated over a protocol solving <span class="math-container">$KW_f$</span>.</p>
</blockquote>
<p>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.</p>
<p>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 <span class="math-container">$NC^1 \neq P$</span> problem.</p>
<p>The first and most basic tool that comes from Communication Complexity are combinatorial rectangles:</p>
<blockquote>
<p>A set <span class="math-container">$R \subseteq X \times Y$</span> is a (combinatorial) rectangle if <span class="math-container">$R = A \times B$</span> for <span class="math-container">$A \subseteq X$</span> and <span class="math-container">$B \subseteq Y$</span>.</p>
<p>Furthermore, given a function <span class="math-container">$f: X \times Y\rightarrow Z$</span> and a rectangle <span class="math-container">$R \subseteq X \times Y$</span>, <span class="math-container">$R$</span> is <em>monochromatic</em> in relation to <span class="math-container">$f$</span> if <span class="math-container">$f$</span> is constant over <span class="math-container">$R$</span>.</p>
</blockquote>
<p>Using rectangles it is possible to partition the space of input of any given function. Given a function <span class="math-container">$f$</span>, the (base 2) logarithm of the amount of rectangles needed to cover the input space of <span class="math-container">$f$</span> gives a lower bound on the communication complexity of any protocol computing such <span class="math-container">$f$</span>.</p>
<p>Here comes my first real question: given a function <span class="math-container">$f:X \times Y \rightarrow Z$</span>, does proving that it is not possible to cover <span class="math-container">$X \times Y$</span> using at most n rectangles imply that <span class="math-container">$CC(f) = \omega(\log(n))$</span>?</p>
<p>Now let’s talk about a practical example. The Equality Function is defined as follows:
<span class="math-container">$$EQ(X,Y) =\begin{cases}
1&amp;\text{if $X = Y$,}\\
0&amp;\text{otherwise.}
\end{cases}$$</span></p>
<p>Since it can be proved using rectangles that <span class="math-container">$CC(EQ) = n + 1$</span>, wouldn’t that mean that <span class="math-container">$D(EQ) = \omega(\log(n))$</span>?</p>
<p>There’s something slipping my grasp, thanks in advance to everyone who will spend some of their time to reply.</p>

CC BY-SA 4.0
2021-04-10T22:30:51.337Z
The complexity class should be denoted ${NC}^1$ rather than $NC'$.
Or Meir
<cc.complexity-theory><complexity-classes><boolean-functions>
KRW Conjecture: separation of NC^1 and P
Pietro D'Amico
# KRW Conjecture: separation of NC^1 and P

(Asked by: username_0 on 2021-04-10)

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.

**Tags:** cc.complexity-theory, complexity-classes, boolean-functions
> **Comments:**
> **username_1**: The complexity class should be denoted ${NC}^1$ rather than $NC'$.  

---

## 1 answers

### Answer by username_1 on 2021-04-10. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Thank you for the exhaustive answer. Of course it is to be proved the lower bound on CC(KWeq) rather than CC(EQ); it was pretty silly of me not to notice it, thanks again for the clear explanation. I have never taken into accounts the changes in the definitions of monochromatic rectangles when talking about relations rather than functions. If I am not getting it wrong, those changes imply monochromatic rectangles being useless with the Karchmer-Wigderson approach. Since every KW relation can be covered using 2n monochromatic rectangles, it would hold CC(KW) >= log 2n for every KW relation.  
> **username_1**: Yes, this is exactly what I meant.  

---

