Finding the Median Requires 2n Comparisons - Samuel W. Bent; John W. John (STOC, 1985)

A New Lower Bound for the Set-Partitioning Problem. - John W. John (SIAM J. Comput., 1988)