We show a new duality between the polynomial margin complexity of f and the discrepancy of the function f 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 − 1 1 , the weakly unbounded-error complexity of f XOR is essentially characterized by the number of points i in the set 0 1 n − 2 for which D f ( i ) = 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 XOR is O ( k log n ) , where k is the odd-even degree of f . We show that the PP complexity of f XOR is ( k log ( n k )) .