Parity Decision Tree Complexity is Greater Than Granularity

Anastasiya Chistopolskaya, Vladimir V. Podolskii

We prove a new lower bound on the parity decision tree complexity ${\mathsf{D}}_{\oplus }(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smalles…