Savicky's function

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]. In particular, [math]DT(G_k) \geq 2^{\Omega(\log^\beta P(G_k))}[/math] for some [math]\beta[/math]. .