Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with granularity:
TR18-174 | 19th October 2018
Anastasiya Chistopolskaya, Vladimir Podolskii

Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

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

ISSN 1433-8092 | Imprint