Difference between revisions of "Rubinstein's sensitivity function"
(Created page with "== 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 <...") |
m |
||
| Line 1: | Line 1: | ||
== Definition == | == 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, and all the rest of bits in the block are <math>-1</math>. | + | 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 == | == 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 [[sensitivity|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. <ref>David Rubinstein, [https://link.springer.com/article/10.1007/BF01200762 Sensitivity versus block sensitivity of Boolean functions], 1995.</ref> | * 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 [[sensitivity|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. <ref>David Rubinstein, [https://link.springer.com/article/10.1007/BF01200762 Sensitivity versus block sensitivity of Boolean functions], 1995.</ref> | ||
Latest revision as of 11:23, 9 March 2021
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]
