We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f circ textsf{XOR}$, called an $textsf{XOR}$ function. Using this duality, we develop polynomial based techniques for understanding the bounded error ($textsf{BPP}$) and the weakly-unbounded error ($textsf{PP}$) communication complexities of $textsf{XOR}$ functions. We show the following. A weak form of an interesting conjecture of Zhang and Shi (Quantum Information and Computation, 2009) (The full conjecture has just been reported to be independently settled by Hatami and Qian (Arxiv, 2017). However, their techniques are quite different and are not known to yield many of the results we obtain here). Zhang and Shi assert that for symmetric functions $f : {0, 1}^n rightarrow {-1, 1}$, the weakly unbounded-error complexity of $f circ textsf{XOR}$ is essentially characterized by the number of points $i$ in the set ${0,1, dots,n-2}$ for which $D_f(i) eq D_f(i+2)$, where $D_f$ is the predicate corresponding to $f$. The number of such points is called the odd-even degree of $f$. We show that the $textsf{PP}$ complexity of $f circ textsf{XOR}$ is $Omega(k/ log(n/k))$. We resolve a conjecture of a different Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree. We obtain a new proof of the exponential separation between $textsf{PP}^{cc}$ and $textsf{UPP}^{cc}$ via an $textsf{XOR}$ function. We provide a characterization of the approximate spectral norm of symmetric functions, affirming a conjecture of Ada et al. (APPROX-RANDOM, 2012) which has several consequences. Additionally, we prove strong $textsf{UPP}$ lower bounds for $f circ textsf{XOR}$, when $f$ is symmetric and periodic with period $O(n^{1/2-epsilon})$, for any constant $epsilon > 0$.
Download