A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

  • Gerth Stølting Brodal
  • Thore Husfeldt

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.
Published
1996-01-01
How to Cite
Brodal, G., & Husfeldt, T. (1996). A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. BRICS Report Series, 3(1). https://doi.org/10.7146/brics.v3i1.19502