A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

Gerth Stølting Brodal
Thore Husfeldt

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

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.