A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth

Gerth Stølting Brodal and Thore Husfeldt

Technical Report, BRICS-RS-96-1, BRICS, Department of Computer Science, Aarhus University, 3 pages, 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.

Copyright notice

Copyright © 1996, BRICS, Department of Computer Science, Aarhus University. All rights reserved.

Online version

brics-rs-96-1.pdf (119 Kb)

BIBTEX entry

@techreport{brics-rs-96-1,
  author = "Gerth St{\o}lting Brodal and Thore Husfeldt",
  institution = "BRICS, Department of Computer Science, Aarhus University",
  issn = "0909-0878",
  month = "January",
  number = "BRICS-RS-96-1",
  pages = "3",
  title = "A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth",
  year = "1996"
}