5
$\begingroup$

In communication complexity, we encounter the complexity measure $\chi(f)$ for $f : \{0,1\}^{2n} \to \{0,1\}$ which is the minimal number of $f$-monochromatic rectangles needed to tile the $2^n \times 2^n$ matrix describing $f$ (where here $f$-monochromatic means that the individual rectangles are either all $0$ or all $1$).

I am wondering what is known about the computational complexity of $\chi(f)$. I would imagine that it cannot be computed in polynomial time for example (and maybe a minimal tiling cannot be verified in polynomial time) but I could not find any references addressing these issues. Is it known to be, say, NP-hard?

Thank you for reading and I'm sorry if I have missed some obvious reference, I am brand new to thinking about communication complexity.

Improve this question
$\endgroup$
3
  • $\begingroup$ By "rectangle" here do you really mean "submatrix"? ("Rectangle" has the connotation of being contiguous, but I doubt that's what you intend.) $\endgroup$
    – Neal Young
    Feb 7 at 18:39
  • $\begingroup$ I don't mean to imply that it is contiguous. By a rectangle in a set $X \times Y$, I just mean a subset of the form $A \times B$ for $A \subset X, B \subset Y$ (this seems to be standard in the communication complexity literature). $\endgroup$
    – user101010
    Feb 7 at 18:55
  • $\begingroup$ Yes, that makes sense. $\endgroup$
    – Neal Young
    Feb 7 at 19:59

1 Answer 1

Reset to default
2
$\begingroup$

When viewing the Boolean matrix as the bipartite adjacency matrix of a bipartite graph, the problem of determining $\chi_1(f)$, that is, partitioning all the $1$s of the matrix into monochromatic rectangles, is the biclique partition problem, which is NP-complete (also for bipartite graphs). Approximation hardness results are also known.

  • Doina Bein, Linda Morales, Wolfgang W. Bein, Charles O. Shields Jr., Z. Meng, Ivan Hal Sudborough: Clustering and the Biclique Partition Problem. HICSS 2008: 475
  • Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, Andreas Karrenbauer: Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. ESA 2014: 235-246

Update 09/02/2022: the above is an answer to a related problem, and does not answer the OP's question. 🤔

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much for this! I have one technical question related to your answer. If $G_f$ is the bipartite graph described by $f$, then as you point out $\chi(f) = \text{bp}(G_f) + \text{bp}(\overline{G_f})$ (where $\text{bp}$ is the bipartite partition number - which as you mention is NP-complete to compute, even for bipartite graphs). I don't understand how knowing $\chi(f)$ tells us $\text{bp}(G_f)$. Are $\text{bp}(G_f)$ and $\text{bp}(\overline{G_f})$ related in a simple way? $\endgroup$
    – user101010
    Feb 9 at 2:23
  • $\begingroup$ Thanks, I missed this. So the above is only a partial answer, or maybe an answer to a closely related question. I'll update my answer accordingly, and look again into the literature. $\endgroup$
    – Hermann Gruber
    Feb 9 at 20:30
  • 1
    $\begingroup$ Perhaps, somewhat related: the gap between $\mathrm{bp}(G)$ and $\mathrm{bp}(\overline{G})$ can be large: there are graphs $G$ with $\mathrm{bp}(G)=t$ but $\mathrm{bp}(\overline{G})\geq t^{\Omega(\log t)}$. This is a consequence of a current progress concerning tilling numbers; see notes at web.vu.lt/mif/s.jukna/boolean/tilling-gaps.html. $\endgroup$
    – Stasys
    Feb 11 at 11:00

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.