A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

Abstract

We present a direct protocol with logarithmic communication that<br />finds an element in the symmetric difference of two sets of different size. This<br />yields a simple proof that symmetric functions have logarithmic circuit depth.