1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – T.... Mar 7 '15 at 22:12
  • $\begingroup$ It is $g$ that satisfies the Hamming weight 1 condition. $\endgroup$ – Yuval Filmus Mar 7 '15 at 23:23
  • $\begingroup$ 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$. $\endgroup$ – T.... Mar 7 '15 at 23:26
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 7 '15 at 23:30
  • 1
    $\begingroup$ Updated my answer, though I'm sure you could work out the details yourself. Working out things yourself is important to obtain a real understanding, let alone the ability to do research. $\endgroup$ – Yuval Filmus Mar 7 '15 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.