Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f:\{0,1{\}}^n\times \{0,1{\}}^n\to \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus…