World's most popular travel blog for travel bloggers.

Particular function communication complexity computation

, , No Comments
Problem Detail: 

Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then communication complexity of function is $\Omega(n)$. This is claim $4.23$ in Jukna's book. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with atleast $r$ number of $n$ of $0/1$ vectors $x$ each of Hamming weight $1$, then is communication complexity of function $\Omega(r)$? Could this possibly have truth?

Asked By : Turbo
Answered By : Yuval Filmus

There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x_1,\ldots,x_r) = f(x_1,\ldots,x_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works for $g$, so we get a lower bound of $\Omega(r)$ for $f$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback