文章基本信息
- 标题：A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth
- 本地全文：下载
- 作者：Gerth Stølting Brodal ; Thore Husfeldt
- 期刊名称：BRICS Report Series
- 印刷版ISSN：0909-0878
- 出版年度：1996
- 卷号：3
- 期号：1
- 出版社：Aarhus University
- 摘要：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.
