We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,
we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. This enables us to show the following.
1) 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$ XOR is essentially characterized by
the number of points $i$ in the set $\{0,1, \dots,n-2\}$ for which $D_f(i) \neq 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 observe that a much earlier work of Zhang implies that the PP complexity of $f \circ$ XOR is $O(k \log n)$, where $k$ is the odd-even degree of $f$.
We show that the PP complexity of $f \circ$ XOR is $\Omega(k/ \log(n/k))$.
2) We resolve a conjecture of Zhang characterizing the Threshold of Parity circuit size of symmetric functions in terms of their odd-even degree.
3) We obtain a new proof of the exponential separation between PP^{cc} and UPP^{cc} via an XOR function.
4) 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.
This also provides a new proof of the characterization of the bounded error complexity of symmetric XOR functions due to Zhang and Shi.
Additionally, we prove strong UPP lower bounds for $f \circ$ XOR, when $f$ is symmetric and periodic with period $O(n^{1/2-\epsilon})$, for any constant $\epsilon > 0$.
More precisely, we show that every such XOR function has unbounded error complexity $n^{\Omega(1)}$, unless $f$ is constant or parity or its complement, in which case the complexity is just $O(1)$.
As a direct consequence of this, we derive new exponential lower bounds on the size of depth-2 threshold circuits computing such XOR functions.
Our UPP lower bounds do not involve the use of linear programming duality.
