|
A Communication Complexity Proof that Symmetric Functions have
Logarithmic Depth
Gerth Stølting Brodal 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. |