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...

詳細記述

書誌詳細
主要な著者: Klauck, Hartmut, Podder, Supartha
その他の著者: School of Physical and Mathematical Sciences
フォーマット: Journal Article
言語:English
出版事項: 2018
主題:
オンライン・アクセス:https://hdl.handle.net/10356/87671
http://hdl.handle.net/10220/46787