Difference between revisions of "Savicky's function"
(Created page.) |
m (→Definition) |
||
| Line 14: | Line 14: | ||
|<math> G_{k+1} = g(G_k^1,G_k^2,G_k^3,G_k^4),</math> | |<math> G_{k+1} = g(G_k^1,G_k^2,G_k^3,G_k^4),</math> | ||
|} | |} | ||
| − | where each <math> | + | where each <math>G_k^i</math> is defined on a disjoint set of variables. In total, the number of variables on which <math>G_k</math> depends is <math>n=4^k</math>. This is Savicky's function. |
== Properties == | == Properties == | ||
Revision as of 10:19, 3 March 2020
Savicky's function shows that there can be a superpolynomial separation between the partition size and the decision tree size of a Boolean function.
Definition
Let [math]g: \{-1,1\}^4 \to \{-1,1\}[/math] be the function
[math] g(x_1, x_2, x_3, x_4) = (x_1 \lor x_2 \lor x_3)x_4 \lor x_1 x_2 x_3.[/math]
In words, [math]g(x)[/math] is 1 if [math]x_4[/math] is 1 and any of [math]x_1,x_2,x_3[/math] are 1, or if all three of [math]x_1,x_2,x_3[/math] are 1.
Using [math]g[/math], we can define a series of functions. Let [math]G_0[/math] be a single variable, and set
[math] G_{k+1} = g(G_k^1,G_k^2,G_k^3,G_k^4),[/math]
where each [math]G_k^i[/math] is defined on a disjoint set of variables. In total, the number of variables on which [math]G_k[/math] depends is [math]n=4^k[/math]. This is Savicky's function.
Properties
- The partition size of [math]G_k[/math] is [math]P(G_k) \leq 2^{3^k}[/math], whereas the decision tree size of [math]G_k[/math] is [math]DT(G_k) = \mathrm{exp}(\Omega(4^k))[/math]. [1].
