Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFourier Growth of Parity Decision Trees
78
0
0.0
(
0
)
Added by
Kewen Wu
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has (randomized) parity decision tree complexity $tilde{Omega}left(n^{1-1/k}right)$, while having quantum query complexity $lceil k/2rceil$. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-$ell$ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-$ell$ walks can be computed by the intermediate values of level $le ell-1$ walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).
rate research
Read More
We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Let f be a Boolean function with Fourier support S and Fourier sparsity k. 1) We prove via the probabilistic method that there exists a parity decision tree of depth O(sqrt k) that computes f. This matches the best known upper bound on the parity decision tree complexity of Boolean functions (Tsang, Wong, Xie, and Zhang, FOCS 2013). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. 2) We generalize the above result by showing that if the Fourier spectra of Boolean functions satisfy a natural folding property, then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(sqrt k). We make a conjecture in this regard which, if true, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS 2013, Lovett, J. ACM. 2016). 3) It can be shown by elementary techniques that for any Boolean function f and all pairs (alpha, beta) of parities in S, there exists another pair (gamma, delta) of parities in S such that alpha + beta = gamma + delta. We show, among other results, that there must exist several gamma in F_2^n such that there are at least three pairs (alpha_1, alpha_2) of parities in S with alpha_1 + alpha_2 = gamma.
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 - mathsf{B}(n)$ on the multiplicative complexity of majority.
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. 1) If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f circ IP$ equals $Omega(n(b-1))$. 2) If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f circ IP$ is at least $Omega(b cdot D_{dt}^{rightarrow}(f))$, where $D_{dt}^{rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$. For our quantum lower bound, we show a lower bound on the VC-dimension of $f circ IP$, and then appeal to a result of Klauck [STOC00]. Our deterministic lower bound relies on a combinatorial result due to Frankl and Tokushige [Comb.99]. It is known due to a result of Montanaro and Osborne [arXiv09] that the deterministic one-way communication complexity of $f circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$. In contrast, we show the following with the gadget $AND_2$. 1) There exists a function for which even the randomized non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f circ AND_2$. 2) For symmetric functions $f$, the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f circ AND_2$. In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f circ AND_2$. The proof of the first point above uses the well-studied Odd-Max-Bit function.
In this note, we study the relation between the parity decision tree complexity of a boolean function $f$, denoted by $mathrm{D}_{oplus}(f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR functions $F(x_1,ldots, x_k)= f(x_1opluscdotsoplus x_k)$, denoted by $mathrm{CC}^{(k)}(F)$. It is known that $mathrm{CC}^{(k)}(F)leq kcdotmathrm{D}_{oplus}(f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that [mathrm{D}_{oplus}(f)leq Obig(mathrm{CC}^{(4)}(F)^5big).] Our main tool is a recent result from additive combinatorics due to Sanders. As $mathrm{CC}^{(k)}(F)$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR functions are polynomially equivalent whenever $kgeq 4$. Remark: After the first version of this paper was finished, we discovered that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.
We give a quasipolynomial-time algorithm for learning stochastic decision trees that is optimally resilient to adversarial noise. Given an $eta$-corrupted set of uniform random samples labeled by a size-$s$ stochastic decision tree, our algorithm runs in time $n^{O(log(s/varepsilon)/varepsilon^2)}$ and returns a hypothesis with error within an additive $2eta + varepsilon$ of the Bayes optimal. An additive $2eta$ is the information-theoretic minimum. Previously no non-trivial algorithm with a guarantee of $O(eta) + varepsilon$ was known, even for weaker noise models. Our algorithm is furthermore proper, returning a hypothesis that is itself a decision tree; previously no such algorithm was known even in the noiseless setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
