Deterministic dynamic dictionary on a small universe

We want to maintain a dictionary of $m$ elements with insert/delete and lookup in the word RAM model. Assume $m=O(n)$ at all times, so there can't be too many inserts without deletions. The universe has size $\{0,\ldots,n^c-1\}$ for some constant $c$.

How fast can we support these operations deterministically (in either worst case or amortized time) if we are restricted to $O(n)$ space? How about $O(n \mathop{\mathrm{polylog}} n)$ space?

A few simple observations:

• When $c=1$, an array of size $n$ support all operations in worst time $O(1)$.

• It's not hard to come up with a $O(n^{1+\epsilon})$ space data structure so all queries can be done in $O(\frac{1}{\epsilon})$ worst case time for any $\epsilon>0$.

• We can implement all operations in worst time $O\left(\frac{(\log \log n)^2}{\log \log \log n}\right)$ with $O(m)$ space using exponential tree.

To clarify, I'm looking for dictionaries with space requirement as a function of the size of the universe, and not the number of elements in the dictionary.

If randomness is allowed, you can get space $B + o(B)$ and time $O(1)$ (worst-case, with high probability), where $B$ is $\lg {U \choose n}$, which is the lower bound on how much space you need using any representation: Arbitman et al., " Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation".
• They frequently have size $O(n \lg m)$. Do you want the space to not include any factor of $n$? – jbapple Dec 12 '13 at 16:42
• Sorry, that's supposed to be $O(n \lg U)$. – jbapple Dec 12 '13 at 16:51
• Yes, I like space of the form $O(U^{1/c})$ (and assume the dictionary never holds more than $U^{1/c}$ elements). The hope is that a relaxed bound can speed up the operations. – Chao Xu Dec 12 '13 at 16:58