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...
| 主要な著者: | , |
|---|---|
| その他の著者: | |
| フォーマット: | Journal Article |
| 言語: | English |
| 出版事項: |
2018
|
| 主題: | |
| オンライン･アクセス: | https://hdl.handle.net/10356/87671 http://hdl.handle.net/10220/46787 |