13. Integer Lower Bounds

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.