We consider dictionaries over the universe
![$U=\{0,1\}^w$](Abs/img1.gif)
on a
unit-cost RAM with word size
![$w$](Abs/img2.gif)
and a standard instruction set. We present a
linear space deterministic dictionary with membership queries in time
![$(\log\log n)^{O(1)}$](Abs/img3.gif)
and updates in time
![$(\log n)^{O(1)}$](Abs/img4.gif)
, where
![$n$](Abs/img5.gif)
is the
size of the set stored. This is the first such data structure to
simultaneously achieve query time
![$(\log n)^{o(1)}$](Abs/img6.gif)
and update time
![$O(2^{\sqrt{\log n}})$](Abs/img7.gif)