We introduce a novel
technique for converting static polynomial space search structures
for ordered sets into fully-dynamic linear space data structures.
Based on this we present optimal bounds for
dynamic integer searching, including finger
search, and exponentially improved bounds for priority queues.
Preprint (postscript)
Preprint (pdf)