  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.
