Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NOISY DECISION TREE:
Reports tagged with noisy decision tree:
TR21-046 | 22nd March 2021
Uma Girish, Avishay Tal, Kewen Wu

#### Fourier Growth of Parity Decision Trees

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$.
Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound ... more >>>

ISSN 1433-8092 | Imprint