Technical Reports

We consider the problem of determining the maximum and minimum elements {x_{1}, \ldots ,x_{n}}$, drawn from some finite universe$\cal U$of real numbers, using only unary predicates of the inputs. It is shown that$\Theta (n + \log |{\cal U} |) \$ unary predicate evaluations are necessary and sufficient, in the worst case. Results are applied to i) the problem of determining approximate extrema of a set of real numbers, in the same model, and ii) the multiparty broadcast communication complexity of determining the extrema of an arbitrary set of numbers held by distinct processors.