Ben-Or's Theorem: Lower Bounds in the Algebraic Computation Tree Model

Carsten Grimm

Ben-Or's theorem is a key ingredient for many known lower bounds on a variety of problems in the algebraic computation tree model. These bounds state, for instance, that deciding whether $n$ real values are distinct, computing the diameter of a set of $n$ points in the plane, and constructing the convex hull each require $\Omega(n \log n)$ time in the worst case. In this talk, we present Ben-Or's theorem together with its proof and we demonstrate how to apply it using a sequence of examples.