# 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 $g: \{-1,1\}^4 \to \{-1,1\}$ be the function

 $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.$

In words, $g(x)$ is 1 if $x_4$ is 1 and any of $x_1,x_2,x_3$ are 1, or if all three of $x_1,x_2,x_3$ are 1.

Using $g$, we can define a series of functions. Let $G_0$ be a single variable, and set

 $G_{k+1} = g(G_k^1,G_k^2,G_k^3,G_k^4),$

where each $G_k^i$ is defined on a disjoint set of variables. In total, the number of variables on which $G_k$ depends is $n=4^k$. This is Savicky's function.

## Properties

• The partition size of $G_k$ is $P(G_k) \leq 2^{3^k}$, whereas the decision tree size of $G_k$ is $DT(G_k) = \mathrm{exp}(\Omega(4^k))$. In particular, $DT(G_k) \geq 2^{\Omega(\log^\beta P(G_k))}$ for some $\beta$. [1].