Address

Definition

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

[math]f(x_1, \ldots, x_k, y_1,\ldots,y_{2^k}) = y_{\tilde{x}}, [/math]

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

Properties

• The influence of one of the [math]k[/math] address bits is 1/2 (changing the address means pointing to a new, independent, data bit). The influence of every one of the [math]2^k[/math] data bits is [math]1/2^{k}[/math] (that's the probability that the address points to that particular bit).
• The degree of [math]f[/math] is [math]d = k+1 \approx \log n[/math]: The Fourier representation is a sum of [math]2^{k}[/math] indicator monomials of the form [math]y_{a}\prod_{i=1}^{k}\left(x_{i}-a_{i}\right)[/math].