Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF]
| [+] Integer: predecessor lower bound via round elimination | ||||
|
This lecture is our first (of two) about integer data structure lower bounds.
In particular, we'll prove that the min of van Emde Boas and
fusion trees is an optimal (static) predecessor data structure up to a
log log factor, assuming polynomial space. The exact trade-off (up to
constant factors) is known, but messier; we'll see the bound but not
prove it. In particular, it is known that the log log factor improvements
are actually impossible to achieve with roughly linear space, making the min
of van Emde Boas and fusion trees actually optimal.
These lower bounds hold in the powerful cell-probe model of computation, where we just count the number of words read by the query algorithm. The proof uses a beautiful technique called round elimination, in a communication-complexity view of data structures, and is actually quite clean and simple given an appropriate lemma. | ||||
|
Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF] |
|
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.