Since 2014
A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth
|
|
| Creator |
Brodal, Gerth Stølting
Husfeldt, Thore |
|
| Description |
We present a direct protocol with logarithmic communication thatfinds an element in the symmetric difference of two sets of different size. Thisyields a simple proof that symmetric functions have logarithmic circuit depth.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1996-01-01
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19502
10.7146/brics.v3i1.19502 |
|
| Source |
BRICS Report Series; No 1 (1996): RS-1 A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth
BRICS Report Series; No 1 (1996): RS-1 A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19502/17124
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|