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.
The Massachusetts Institute of Technology (MIT), founded in 1861, is located in Cambridge, Massachusetts, and is one of the foremost U.S. institutions in science and technology. It is comprised of five schools and one college, including the renowned School of Engineering and Sloan School of Management, offering Bachelor's, Master's, and Doctorate degrees. Notable alumni include Ben Bernanke, Chairman of the Federal Reserve, Benjamin Netanyahu, prime minister of Israel, and American astronaut "Buzz" Aldrin.