<p>When viewing the Boolean matrix as the bipartite adjacency matrix of a bipartite graph, the problem of determining <span class="math-container">$\chi_1(f)$</span>, that is, partitioning all the <span class="math-container">$1$</span>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.</p>
<ul>
<li>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</li>
<li>Parinya Chalermsook, Sandy Heydrich, Eugenia Holm, Andreas Karrenbauer: Nearly Tight Approximability Results for Minimum Biclique Cover and Partition. ESA 2014: 235-246</li>
</ul>
<p><em>Update 09/02/2022:</em> the above is an answer to a related problem,  and does not answer the OP's question. </p>

CC BY-SA 4.0
2022-02-09T02:23:09.467Z
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?
user101010
CC BY-SA 4.0
2022-02-09T20:30:28.603Z
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.
Hermann Gruber
CC BY-SA 4.0
2022-02-11T11:00:30.597Z
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  https://web.vu.lt/mif/s.jukna/boolean/tilling-gaps.html.
Stasys
CC BY-SA 4.0
2022-02-08T08:31:26.630Z
2022-02-09T20:37:45.910Z
2022-02-09T20:37:45.910Z
Hermann Gruber
<p>In communication complexity, we encounter the complexity measure <span class="math-container">$\chi(f)$</span> for <span class="math-container">$f : \{0,1\}^{2n} \to \{0,1\}$</span> which is the minimal number of <span class="math-container">$f$</span>-monochromatic rectangles needed to tile the <span class="math-container">$2^n \times 2^n$</span> matrix describing <span class="math-container">$f$</span> (where here <span class="math-container">$f$</span>-monochromatic means that the individual rectangles are either all <span class="math-container">$0$</span> or all <span class="math-container">$1$</span>).</p>
<p>I am wondering what is known about the computational complexity of <span class="math-container">$\chi(f)$</span>.  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?</p>
<p>Thank you for reading and I'm sorry if I have missed some obvious reference, I am brand new to thinking about communication complexity.</p>

CC BY-SA 4.0
2022-02-07T18:39:38.750Z
By "rectangle" here do you really mean "submatrix"?  ("Rectangle" has the connotation of being contiguous, but I doubt that's what you intend.)
Neal Young
CC BY-SA 4.0
2022-02-07T18:55:01.140Z
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).
user101010
CC BY-SA 4.0
2022-02-07T19:59:19.153Z
Yes, that makes sense.
Neal Young
<reference-request><communication-complexity>
Complexity of Yao's tiling number?
user101010
# Complexity of Yao's tiling number?

(Asked by: username_0 on 2022-02-07)

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.

**Tags:** reference-request, communication-complexity

> **Comments:**
> **username_1**: By "rectangle" here do you really mean "submatrix"?  ("Rectangle" has the connotation of being contiguous, but I doubt that's what you intend.)  
> **username_0**: 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).  
> **username_1**: Yes, that makes sense.  

---

## 1 answers

### Answer by username_2 on 2022-02-08. Score: 2

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  
> **username_3**: 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  https://web.vu.lt/mif/s.jukna/boolean/tilling-gaps.html.  

---

