All reports by Author Anastasiya Chistopolskaya:

__
TR18-174
| 19th October 2018
__

Anastasiya Chistopolskaya, Vladimir Podolskii#### Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

Anastasiya Chistopolskaya, Vladimir Podolskii

We prove a new lower bound on the parity decision tree complexity $D_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $D_{\oplus}(f)\geq k+1$.

This lower bound is ... more >>>