Michiel Smid

Given a sequence *A* of 2*n* real numbers, the EvenRankSum problem asks for
the sum of the *n* values that are at the even positions in the sorted
order of the elements in *A*. We prove that, in the algebraic
computation-tree model, this problem has time complexity
Θ(*n*log *n*). This solves an open problem posed by
Michael Shamos at the Canadian Conference on Computational Geometry
in 2008. (Joint work with Marc Mörig, Dieter Rautenbach, and Jan Tusch.)