Let $X_0, \ldots, X_{2^n-1}$ be $k$-wise independent random $0/1$ variables over a sample space $\Omega$ and $Prob \left[ X_i = 1 \right] = p$ for every $i$ and some $0 < p < 1$. Let assume $n$ is dividable by 2 and $f(x,y): \lbrace 0,1 \rbrace^{n/2} \times \lbrace 0,1 \rbrace^{n/2} \rightarrow \lbrace 0,1 \rbrace$ is defined by $f(x,y) = X_{\vert xy \vert}$ where $xy$ is the concatenation of $x$ and $y$ and $\vert z \vert := \sum 2^i \cdot z_i$. I'm interested in the 1-way 2-party (deterministic) communication complexity of $f$ such that both players know the random sample (out of $\Omega$) which is chosen at the beginning of the protocol, i.e. both players know the current value of every $X_i$. Of course, it is also ok to know something about the expected number of communicated bits.

Motivation: At first I think this is an interesting problem :) However, I'm currently dealing with such random functions and want to show some lower bounds for my computational model using communication complexity.

  • $\begingroup$ the rows of the hadamard matrix $H_{x,y} = (-1)^{\langle x, y \rangle}$ form a pairwise-independent hash family. but if you split $y$ into two $n/2$-bit pieces $y_1, y_2$, for any $x$ the first party just needs to compute $f(x, y_1)= (-1)^{\langle x, y_1 \rangle}$ and send that single bit to the other party to compute $f(x, y_1)\cdot f(x, y_2) = H_{x,y_1 y_2}$ $\endgroup$ Oct 5, 2012 at 17:04
  • $\begingroup$ @SashoNikolov yes that's true. Another possibility is to consider the inner product of a random vector and the input to construct pairwise independent random variables. But this is only the case of $p=1/2$. Does it hold for arbitrary $p$? $\endgroup$
    – Marc Bury
    Oct 5, 2012 at 23:07


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.