# Complexity of Yao's tiling number?

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.

• By "rectangle" here do you really mean "submatrix"? ("Rectangle" has the connotation of being contiguous, but I doubt that's what you intend.) Feb 7 at 18:39
• 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). Feb 7 at 18:55
• Yes, that makes sense. Feb 7 at 19:59

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.
• 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? Feb 9 at 2:23
• 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. Feb 11 at 11:00