Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANASTASIYA CHISTOPOLSKAYA:
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

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