0
$\begingroup$

I have encountered this question when reading Razborov's communication complexity survey.

The function $\text{DISJ}_n$ is defined on $\{0, 1\}^n\times \{0, 1\}^n$ as $$\text{DISJ}_n(x, y) = 1 \iff \forall i\le n : x_i = 0\lor y_i = 0\;,$$ that is, the sets of positions where the strings $x$ and $y$ have a $1$ are disjoint. Prove that $C(\text{DISJ}_n)\ge \Omega(n)$.

Hint. How many points $(x, y)$ with $\text{DISJ}_n(x, y) = 1$ do we have? And what is the maximal size of a 1-rectangle?

Where $C(\text{DISJ}_n)$ is communication complexity of $\text{DISJ}_n$ function.

It is easy to know that there are $3^n$ points with $\text{DISJ}_n(x,y)=1$. The final thing is finding the maximal size of a 1-rectangle, i.e., the set of points have same transcript s.t. $\text{DISJ}_n(x,y)=1$.

I guess that size is $2^{n+n/2}$. However, all thing I can do to prove a contradiction is limited.

My try:

Assume that the maximal size of 1-rectangle is more than $2^{n+n/2}$. According to Dirichlet's principle, there are more than $2^{n/2}$ points $(x,y)$ have same $x$ part, say $x'$. Similarly, there are more than $2^{n/2}$ points $(x,y)$ have same $y$ part, say $y'$.

There must be two strings $z_1,z_2$ have same first $n/2$ bits s.t. $(x',z_1)$ and $(z_2,y')$ in the same 1-rectangle, so do $(z_2,z_1)$. Thus, the first $n/2$ bits of $z_1,z_2$ must be $0^{n/2}$.

Now I'm getting stuck since I cannot infer any further contradiction. Could you please help me continue proving? Thanks in advance!!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

$\newcommand{\barx}{\overline{x}}\newcommand{\bary}{\overline{y}}\newcommand{\disj}{\text{DISJ}_n}$ Let $\barx$ be the reverse bit string of $x$.

We construct the fooling set $L=\{(x,\barx)|x\in\{0,1\}^n\}$. It is easy to see that $\disj(x,\barx)=1$. We will show that any two elements of $L$ cannot have the same communication transcript.

Consider $(x,\barx)$ and $(y,\bary)$, where $x\neq y$, assume that their communication transcripts are same. So communication transcripts of $(x,\barx),(y,\bary),(x,\bary),(y,\barx)$ are also same. As a result, $\disj(x,\bary)=\disj(y,\barx)=1$.

Let $x_i,y_i,\barx_i,\bary_i$ be $i$th entries of $x,y,\barx,\bary$, respectively. For all $i$, if $x_i=\bary_i=0$, then $y_i=\barx_i=1$ which contradicts the assumption $\disj(y,\barx)=1$. Consequently, $\forall i\le n\;x_i\neq\bary_n$, which means $\forall i\le n\;x_i=y_i$. Contradiction!

Because $|L|=2^n$ so $CC(\disj)\ge\log(|L|)=n$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.