# 0-partition number vs partition number

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)$?

• Maybe you can get the separation from here cs.toronto.edu/~toni/Papers/partition.pdf – Sasho Nikolov Apr 25 '18 at 0:33
• @SashoNikolov I think the paper you link (and this one, 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. Apr 25 '18 at 4:30
• 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 Apr 25 '18 at 14:52
• @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. Apr 25 '18 at 16:21
• @SajinKoroth I think that the lower bound is improved to $2-o(1)$ in the exponent by Kothari et al. – withhighprob Apr 25 '18 at 16:25

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.
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$.
• 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 Apr 26 '18 at 8:11
• @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. Apr 27 '18 at 19:40