Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.
We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.
This relies on a novel technique ... more >>>

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 >>>

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 >>>

We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation $f \circ g$ as long as the gadget $g$ satisfies a property that we call stifling. We observe that several simple ... more >>>

Direct sum theorems state that the cost of solving $k$ instances of a problem is at least $\Omega(k)$ times
the cost of solving a single instance. We prove the first such results in the randomised parity
decision tree model. We show that a direct sum theorem holds whenever (1) the ... more >>>