New bounds for the garden-hose model
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown Theta(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n * log^3(n) upper bound for the Distribut...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/87671 http://hdl.handle.net/10220/46787 |