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 ... more >>>