6
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Maybe you can get the separation from here cs.toronto.edu/~toni/Papers/partition.pdf $\endgroup$ – Sasho Nikolov Apr 25 '18 at 0:33
  • 2
    $\begingroup$ @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. $\endgroup$ – Clement C. Apr 25 '18 at 4:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Robin Kothari Apr 25 '18 at 14:52
  • 2
    $\begingroup$ @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$? $\endgroup$ – Clement C. Apr 25 '18 at 16:21
  • 1
    $\begingroup$ @SajinKoroth I think that the lower bound is improved to $2-o(1)$ in the exponent by Kothari et al. $\endgroup$ – sagnik Apr 25 '18 at 16:25
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sagnik Apr 26 '18 at 8:11
  • $\begingroup$ @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})$. $\endgroup$ – Clement C. Apr 27 '18 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.