# Particular function communication complexity computation

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?

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$.
• Thank you. I am sorry $f(\underbrace{0,\dots,0}_{r\text{ times}},\dots,\underbrace{1,\dots,1}_{r\text{ times}},\dots,\underbrace{0,\dots,0}_{r\text{ times}})$ where each sequence of $0/1$ is $r$ in length will have no guarantee to be $1$ since $(\underbrace{0,\dots,0}_{r\text{ times}},\dots,\underbrace{1,\dots,1}_{r\text{ times}},\dots,\underbrace{0,\dots,0}_{r\text{ times}})$ does not have Hamming weight $1$. Am I missing something? – T.... Mar 7 '15 at 22:12
• It is $g$ that satisfies the Hamming weight 1 condition. – Yuval Filmus Mar 7 '15 at 23:23
• I understand that input to $g$ is of Hamming weight $1$. However, you are expanding input aritifically by repeating $0$s/$1$s. $f$ satisfies $f(x)=1$ when $|x|_{HAMM}=1$ with atmost $r<n$ such $x$ vectors. Expanded input to $f$ is no longer hamming weight $1$. – T.... Mar 7 '15 at 23:26
• Ah, now I understand your question. A similar reduction would work for your actual question. Pick the $r$ good coordinates and fix the rest to zero. Then you get an $\Omega(r)$ lower bound. – Yuval Filmus Mar 7 '15 at 23:30