Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > FAITH FICH:
All reports by Author Faith Fich:

TR98-028 | 28th May 1998
Paul Beame, Faith Fich

On Searching Sorted Lists: A Near-Optimal Lower Bound


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




ISSN 1433-8092 | Imprint