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