A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth - Brodal, Gerth Stølting; Husfeldt, Thore (BRICS Report Series, 1996)
We present a direct protocol with logarithmic communication that finds an element in the symmetric difference of two sets of different size. This yields a simple proof that symmetric functions have logarithmic circuit depth.