A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

Gerth Stølting Brodal
Thore Husfeldt

January 1996

Abstract:

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.