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

Full description

Saved in:
Bibliographic Details
Main Authors: Klauck, Hartmut, Podder, Supartha
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2018
Subjects:
Online Access:https://hdl.handle.net/10356/87671
http://hdl.handle.net/10220/46787
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English

Similar Items