World's most popular travel blog for travel bloggers.

# Particular function communication complexity computation

, ,
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?

###### 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$.