## Definition

Let $n = k + 2^k$. A function $f:\{-1,1\}^n \to \{-1,1\}$ is called an address function if it returns the bit pointed to by the first $k$ bits:

 $f(x_1, \ldots, x_k, y_1,\ldots,y_{2^k}) = y_{\tilde{x}},$

where $\tilde{x}$ is number whose binary representation of the vector $(x_1,\ldots, x_k)$.