Difference between revisions of "Address"
(→Properties) |
m |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
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: | 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> | + | :::{| class="wikitable" |
| + | |- | ||
| + | |<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>. | + | where <math>\tilde{x}</math> is number whose binary representation of the vector <math>(x_1,\ldots, x_k)</math>. |
== Properties == | == 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>. | ||
== References == | == References == | ||
<references/> | <references/> | ||
| + | |||
| + | [[Category:balanced function]] [[Category:Noise sensitive function]] | ||
Latest revision as of 14:59, 7 April 2021
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].
