Communication complexity in linearly ordered sets

Abstract

In this paper we consider a communication complexity of the minimum function defined over a linear ordered set. We construct a protocol, the cost of which give an upper bound on the deterministic communication complexity. A lower bound will be derived from the rank lower bound. It seems, that the presented protocol is almost optimal for large sets. Its simply modification give an upper bound on the average communication complexity of the minimum function.