A New Trade-off for Deterministic Dictionaries

We consider dictionaries over the universe U = {0, 1}^w on a unit-costRAM with word size w and a standard instruction set. We presenta linear space deterministic dictionary with membership queries intime (log log n)^O(1) and updates in time (log n)^O(1), where n is the sizeof the set stored. This is the first such data structure to simultaneouslyachieve query time (log n)^o(1) and update time O(2 ^sqrt log n) )