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

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Maybe you can get the separation from here cs.toronto.edu/~toni/Papers/partition.pdf $\endgroup$
    – Sasho Nikolov
    Commented Apr 25, 2018 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.
    Commented Apr 25, 2018 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
    Commented Apr 25, 2018 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.
    Commented Apr 25, 2018 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$
    – withhighprob
    Commented Apr 25, 2018 at 16:25

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
2
  • $\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$
    – withhighprob
    Commented Apr 26, 2018 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.
    Commented Apr 27, 2018 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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