<p>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 &lt; p &lt; 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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-05T17:04:47.163Z
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}$
Sasho Nikolov
CC BY-SA 3.0
2012-10-05T23:07:32.000Z
@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$?
Marc Bury
<cc.complexity-theory><randomness><communication-complexity>
Communication complexity of random functions with limited independence
Marc Bury
# Communication complexity of random functions with limited independence

(Asked by: username_0 on 2012-10-05)

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.

**Tags:** cc.complexity-theory, randomness, communication-complexity

> **Comments:**
> **username_1**: 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}$  
> **username_0**: @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$?  

---

## 0 answers

