<p>A quadratic separation between $\log\chi_0$ and $\log\chi_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the <a href="https://eccc.weizmann.ac.il/report/2015/169/" rel="noreferrer">ECCC report</a>.</p>

<p>In Theorem 2 they construct a function $F$ with small $\log\chi_1(F)$, and they say "In fact, we prove Theorem 2 by showing that (the negation of) the function $F$ has high approximate nonnegative rank". Observe that $\log\chi_0(F)$ is at least the nonnegative rank of the negation of $F$.</p>

CC BY-SA 3.0
2018-04-26T08:11:52.353Z
Perfect. I guess, for the parameters stated in the paper and ignoring log, the function $F$ has: $\log \chi_1(F) = O(N^{1/3})$ and $\log \chi_0(F) \geq \log rk^{+}(\bar F) \geq \Omega(N^{2/3})$ where $N$ is the input length. Please correct me if I am wrong.
withhighprob
CC BY-SA 3.0
2018-04-27T19:40:05.850Z
@sagnik From what I understood reading the paper, that's correct, up to some $\log$'s. $\log \chi_1(F) = \tilde{O}(N^{1/3})$, $\log \operatorname*{rank}^+(\bar{F}) = \tilde{\Omega}(N^{2/3})$.
Clement C.
CC BY-SA 3.0
2018-04-25T18:15:22.753Z
2018-04-26T07:22:47.350Z
2018-04-26T07:22:47.350Z
Raskolnikov
<p>Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all inputs of $f$ (both 0 and 1). It is known that</p>

<p>$$\log \chi(f) \leq D(f) \leq (\log \chi_0(f))^2.$$</p>

<p>The last inequality follows from the famous clique vs independent set upper bound. Is there an $f$ that witnesses such a quadratic separation between $\log \chi(f)$ and $\log \chi_0(f)$?</p>

CC BY-SA 3.0
2018-04-25T00:33:52.853Z
Maybe you can get the separation from here https://www.cs.toronto.edu/~toni/Papers/partition.pdf
Sasho Nikolov
CC BY-SA 3.0
2018-04-25T04:30:13.973Z
@SashoNikolov I think the paper you link (and [this one](https://arxiv.org/abs/1512.01210), which improves on one of its results) doesn't give such separation. They show the existence of *some* $f$ for which the lower bound "goes up" (e.g., $D(f\geq \log^{2-\epsilon}\chi(f)$ or $D(f\geq \log^{1+c}\chi_0(f)$), but neither the former nor the latter gives a separation or general relation between $\log \chi_0$ and $\log \chi$, or at least they don't discuss it.
Clement C.
CC BY-SA 3.0
2018-04-25T14:52:46.450Z
I don't know if anyone has proved this, but I believe the function that quadratically separates deterministic communication from 0-partition number should also quadratically separate partition number from 0-partition number.
Robin Kothari
CC BY-SA 3.0
2018-04-25T15:16:58.627Z
Since $\chi(f)=\chi_1(f)+\chi_0(f)$, if there is a function for which $\log \chi_0(f) \leq \sqrt{\log \chi(f)}$, then it must be that $\chi_1(f) \geq \frac{\chi(f)}{2}$. Hence the question can be rephrased as whether there exists a function for which $\log \chi_1(f) = \Omega(\log^2 \chi_0(f))$. 
I think it is also equally interesting to know whether there exists a function for which $\log \chi_0(f) = \Omega(\log^2 \chi_1(f))$.
Sajin Koroth
CC BY-SA 3.0
2018-04-25T15:20:29.407Z
Also if it can be proved that for any $f$, it holds that $\log \chi_0(f) < (\log \chi_1(f))^{1+\epsilon}$ for $\epsilon <2/3$, then one can
improve the gap between $D(f)$ and $\log \chi(f)$ to $D(f) = \tilde{\Omega}(\log^{2-2\epsilon} \chi(f))$. Remember that the best known lower bound for $D(f)$ in terms of $\chi(f)$ is $\tilde{\Omega}(\log^{1.5} \chi(f))$, whereas the best known upper bound is $O(\log^2 \chi(f))$.
Sajin Koroth
CC BY-SA 3.0
2018-04-25T15:24:37.663Z
The lower bound $D(f) \geq \tilde{\Omega}(\log \chi_1(f))$, implies the Clique vs Independent Set problem requires $\tilde{\Omega}(\log^2 n)$ communication. For Clique vs Independent set problem $\chi_1(f) \leq \log n$. We get that $\log \chi_0(f) = (\log n)^{1+\epsilon}$. This implies that for CIS, under our assumption, $\log \chi(f) = O((\log n)^{1+\epsilon})$. Since we assumed, $D(f) = O(\log^{2-2\epsilon} \chi(f))$, we get that $D(f)=O((\log n)^{(1+\epsilon)\cdot(2-
2\epsilon)})$. This is a contradiction.
Sajin Koroth
CC BY-SA 3.0
2018-04-25T15:30:37.593Z
Sorry, it should be "Also if it can be proved that for any $f$, it holds that $\log \chi_0(f) < (\log \chi_1(f))^{1+\epsilon}$ for $\epsilon >0$"
Sajin Koroth
CC BY-SA 3.0
2018-04-25T16:21:50.750Z
@SajinKoroth I haven't add coffee yet, so may be missing the point, but in your first comment... if I have $f$ witnessing $\log \chi_1(f) = \Omega(\log^2 \chi_0(f))$, don't I have the other way around immediately by considering the negation of $f$?
Clement C.
CC BY-SA 3.0
2018-04-25T16:23:28.787Z
@ClementC. Yes. That's true. Maybe I should've had some coffee before writing that.
Sajin Koroth
CC BY-SA 3.0
2018-04-25T16:25:47.777Z
@SajinKoroth I think that the lower bound is improved to $2-o(1)$ in the exponent by Kothari et al.
withhighprob
CC BY-SA 3.0
2018-04-25T16:26:50.363Z
@sagnik Thanks for pointing that out. I didn't know that.
Sajin Koroth
<cc.complexity-theory><communication-complexity>
0-partition number vs partition number
withhighprob
# 0-partition number vs partition number

(Asked by: username_0 on 2018-04-24)

Denote by $\chi\_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all inputs of $f$ (both 0 and 1). It is known that

$$\log \chi(f) \leq D(f) \leq (\log \chi\_0(f))^2.$$

The last inequality follows from the famous clique vs independent set upper bound. Is there an $f$ that witnesses such a quadratic separation between $\log \chi(f)$ and $\log \chi\_0(f)$?

**Tags:** cc.complexity-theory, communication-complexity
> **Comments:**
> **username_1**: Maybe you can get the separation from here https://www.cs.toronto.edu/~toni/Papers/partition.pdf  
> **username_2**: @SashoNikolov I think the paper you link (and [this one](https://arxiv.org/abs/1512.01210), which improves on one of its results) doesn't give such separation. They show the existence of *some* $f$ for which the lower bound "goes up" (e.g., $D(f\geq \log^{2-\epsilon}\chi(f)$ or $D(f\geq \log^{1+c}\chi_0(f)$), but neither the former nor the latter gives a separation or general relation between $\log \chi_0$ and $\log \chi$, or at least they don't discuss it.  
> **username_3**: I don't know if anyone has proved this, but I believe the function that quadratically separates deterministic communication from 0-partition number should also quadratically separate partition number from 0-partition number.  
> **username_4**: Since $\chi(f)=\chi_1(f)+\chi_0(f)$, if there is a function for which $\log \chi_0(f) \leq \sqrt{\log \chi(f)}$, then it must be that $\chi_1(f) \geq \frac{\chi(f)}{2}$. Hence the question can be rephrased as whether there exists a function for which $\log \chi_1(f) = \Omega(\log^2 \chi_0(f))$.  I think it is also equally interesting to know whether there exists a function for which $\log \chi_0(f) = \Omega(\log^2 \chi_1(f))$.  
> **username_4**: Also if it can be proved that for any $f$, it holds that $\log \chi_0(f) < (\log \chi_1(f))^{1+\epsilon}$ for $\epsilon <2/3$, then one can improve the gap between $D(f)$ and $\log \chi(f)$ to $D(f) = \tilde{\Omega}(\log^{2-2\epsilon} \chi(f))$. Remember that the best known lower bound for $D(f)$ in terms of $\chi(f)$ is $\tilde{\Omega}(\log^{1.5} \chi(f))$, whereas the best known upper bound is $O(\log^2 \chi(f))$.  
> **username_4**: The lower bound $D(f) \geq \tilde{\Omega}(\log \chi_1(f))$, implies the Clique vs Independent Set problem requires $\tilde{\Omega}(\log^2 n)$ communication. For Clique vs Independent set problem $\chi_1(f) \leq \log n$. We get that $\log \chi_0(f) = (\log n)^{1+\epsilon}$. This implies that for CIS, under our assumption, $\log \chi(f) = O((\log n)^{1+\epsilon})$. Since we assumed, $D(f) = O(\log^{2-2\epsilon} \chi(f))$, we get that $D(f)=O((\log n)^{(1+\epsilon)\cdot(2- 2\epsilon)})$. This is a contradiction.  
> **username_4**: Sorry, it should be "Also if it can be proved that for any $f$, it holds that $\log \chi_0(f) < (\log \chi_1(f))^{1+\epsilon}$ for $\epsilon >0$"  
> **username_2**: @SajinKoroth I haven't add coffee yet, so may be missing the point, but in your first comment... if I have $f$ witnessing $\log \chi_1(f) = \Omega(\log^2 \chi_0(f))$, don't I have the other way around immediately by considering the negation of $f$?  
> **username_4**: @ClementC. Yes. That's true. Maybe I should've had some coffee before writing that.  
> **username_0**: @SajinKoroth I think that the lower bound is improved to $2-o(1)$ in the exponent by Kothari et al.  
> **username_4**: @sagnik Thanks for pointing that out. I didn't know that.  

---

## 1 answers

### Answer by username_5 on 2018-04-25. Score: 8 | Accepted answer

A quadratic separation between $\log\chi\_0$ and $\log\chi\_1$ is proved in a paper by Göös, Jayram, Pitassi and Watson, see the [ECCC report](https://eccc.weizmann.ac.il/report/2015/169/).

In Theorem 2 they construct a function $F$ with small $\log\chi\_1(F)$, and they say "In fact, we prove Theorem 2 by showing that (the negation of) the function $F$ has high approximate nonnegative rank". Observe that $\log\chi\_0(F)$ is at least the nonnegative rank of the negation of $F$.

> **Comments:**
> **username_0**: Perfect. I guess, for the parameters stated in the paper and ignoring log, the function $F$ has: $\log \chi_1(F) = O(N^{1/3})$ and $\log \chi_0(F) \geq \log rk^{+}(\bar F) \geq \Omega(N^{2/3})$ where $N$ is the input length. Please correct me if I am wrong.  
> **username_2**: @sagnik From what I understood reading the paper, that's correct, up to some $\log$'s. $\log \chi_1(F) = \tilde{O}(N^{1/3})$, $\log \operatorname*{rank}^+(\bar{F}) = \tilde{\Omega}(N^{2/3})$.  

---

