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 |