A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

Authors

  • Gerth Stølting Brodal
  • Thore Husfeldt

DOI:

https://doi.org/10.7146/brics.v3i1.19502

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.

Downloads

Published

1996-01-01

How to Cite

Brodal, G. S., & 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