Rubinstein's sensitivity function
Definition
Let [math] n = 4k^2[/math] be an even square, and define a function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] as follows. Divide the [math]n[/math] inputs into [math]\sqrt{n}[/math] disjoint blocks of size [math]\sqrt{n}[/math]: [math]B_1 = (x_1, \ldots, x_{\sqrt{n}}), B_2 = (x_{\sqrt{n}+1}, \ldots, x_{2\sqrt{n}}),\ldots [/math]. Then [math]f(x) = 1[/math] if and only if there is a block with two consecutive [math]1[/math]'s in indices [math]2j, 2j+1[/math] for some [math]j[/math], and all the rest of bits in the block are [math]-1[/math].
Properties
- The sensitivity of [math]f[/math] is [math]s(f) = \sqrt{n}[/math] (consider the case where there is only one block which satisfies the condition). The block sensitivity of [math]f[/math] is [math]bs(f) = n /2[/math] (consider [math]x = 0[/math]). Thus there is a quadratic separation between sensitivity and block sensitivity. [1]
