Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR18-174 | 26th October 2018 20:23

Parity Decision Tree Complexity is Greater Than Granularity

RSS-Feed




Revision #2
Authors: Anastasiya Chistopolskaya, Vladimir Podolskii
Accepted on: 26th October 2018 20:23
Downloads: 1593
Keywords: 


Abstract:

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 an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - B(n)+1$, where $B(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight.

Our results imply new lower bound of $n - B(n)$ on the multiplicative complexity of majority.



Changes to previous version:

We added a comparison of the complexity measures discussed to the degree of Boolean functions over $\mathbb{F}_2$. We removed the section on $MOD^3$ as a non-instructive example. We added the connection to multiplicative complexity.


Revision #1 to TR18-174 | 26th October 2018 20:11

Parity Decision Tree Complexity is Greater Than Granularity





Revision #1
Authors: Anastasiya Chistopolskaya, Vladimir Podolskii
Accepted on: 26th October 2018 20:11
Downloads: 540
Keywords: 


Abstract:

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 smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $\mathsf{D}_{\oplus}(f)\geq k+1$.

This lower bound is an improvement of lower bounds through the sparsity of $f$ and through the degree of $f$ over $\mathbb{F}_2$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority and recursive majority. For majority the complexity is $n - \mathsf{B}(n)+1$, where $\mathsf{B}(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. Finally, we provide an example of a function for which our lower bound is not tight.

Our results imply new lower bound of $n - \bin(n)$ on the multiplicative complexity of majority.



Changes to previous version:

We added a comparison of the complexity measures discussed to the degree of Boolean functions over $\mathbb{F}_2$. We removed the section on MOD^3 as a non-instructive example. We added the connection to multiplicative complexity.


Paper:

TR18-174 | 19th October 2018 23:10

Parity Decision Tree Complexity is Greater Than Granularity





TR18-174
Authors: Anastasiya Chistopolskaya, Vladimir Podolskii
Publication: 20th October 2018 14:28
Downloads: 763
Keywords: 


Abstract:

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 an improvement of the known lower bound through the sparsity of $f$. Using our lower bound we determine the exact parity decision tree complexity of several important Boolean functions including majority, recursive majority and $MOD^3$ function. For majority the complexity is $n - B(n)+1$, where $B(n)$ is the number of ones in the binary representation of $n$. For recursive majority the complexity is $\frac{n+1}{2}$. For $MOD^3$ the complexity is $n-1$ for $n$ divisible by 3 and is $n$ otherwise. Finally, we provide an example of a function for which our lower bound is not tight.



ISSN 1433-8092 | Imprint