# Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $$g(i,j)$$, which is an arbitrary boolean-valued function over $$i,j \in \{a,b\}^*$$, such that $$|i| = |j| = m.$$ Moreover, we can also say that $$g$$ has communication complexity $$c(m),$$ and we let $$L = \{ij \mid g(i,j) = 1\}.$$

Would it be accurate to say that if $$c(m) = O(1),$$ then $$L$$ is regular? I'm not entirely sure that this is the case. I've been trying to think about counterexamples to this statement, but I can't really think of any. I do know that the converse is true, namely that if $$L$$ is regular, then $$c(m) = O(1)$$. I've been racking my brain over this in the past few days. Any ideas?

• Please do not delete a question after you have received an useful response. We want to keep your question and any answers to them, so that we do not only help you, but also others with a similar question. Oct 9 '20 at 8:23
• Please don't vandalize your posts. By posting on the Stack Exchange network, you've granted a non-revocable right, under the CC BY-SA 4.0 license, for Stack Exchange to distribute that content (i.e. regardless of your future choices). By Stack Exchange policy, the non-vandalized version of the post is the one which is distributed, and thus, any vandalism will be reverted. If you want to know more about deleting a post please see: How does deleting work? Jun 27 at 2:51

No. Let $$L_0$$ be a context-free language, say the language of matched parentheses, $$L_1 = \Sigma^* \setminus L_0$$, and
$$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$
Then $$L$$ is not regular, but it has communication complexity $$O(1)$$.
Let $$L'$$ be an arbitrary language, and consider $$L = \{ \Sigma^{|x|} x : x \in L' \}.$$ Then $$L$$ has roughly the same complexity as $$L'$$, but it has communication complexity $$1$$.