Partition size

Definition

Let [math]f: \{-1,1\}^n \to \{-1,1\}[/math] be a Boolean function. The partition size of [math]f[/math], often denoted [math]P(f)[/math], is the minimum size of a partition of the Boolean cube [math]\{-1,1\}^n[/math] into disjoint subcubes such that [math]f[/math] is constant on each subcube.

Properties

• The partition size is (trivially) always smaller than the decision tree size, [math]P(f) \leq DT(f) [/math].
• The sum of the singleton Fourier coefficients is always smaller than the square root of of the partition size: [math]\sum_{i\in [n]} \widehat{f}(\{i\}) \leq \sqrt{\log(P(f))}[/math]. In particular, if [math]f[/math] is monotone, then [math]\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}[/math] .