Bounds on approximating frequency moments
There's been a fair bit of progress. On the specific problem of $F_k$, there is a matching upper and lower bound of $n^{1-2/k}$ for $k &gt; 2$. The upper bounds come from this paper by Indyk and Woodruff (which appeared in STOC 2005) and the lower bounds are via the information complexity framework, due to Bar-Yossef et al and Chakrabarti et al.