We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's fusion trees and Andersson's search data structure.
Thus they show sharp limitations on the running time improvements
obtainable using the unit-cost word-level RAM operations that those
algorithms employ.