# 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]
^{[1]}.

## References

- ↑ Ryan O'Donnell, Rocco Servedio, Learning Monotone Functions from Random Examples in Polynomial Time