Others

Beating sorting lower bounds

There is an O(nlog(n)) sorting lower bound for comparison based sorts, however, in this talk we'll see a new model for computation, the word RAM model, and data structures based on this model, which solve the Predecessor Problem efficiently leading to O(nsqrt(log(n))) and usage of bit tricks in manipulating numbers. The data structures that we'll primarily see include the van Embde Boas Trees (FOCS '75) and an introduction to Y-Fast Tries.