Single-pass streaming quantile estimation using moments Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f \in o(n)$? If so, what is the most slowly growing $f$ that will suffice?

By "estimate the quantiles", I mean:


  ... for any given rank $r$, an $\epsilon$-approximate quantile summary returns a value whose rank $r'$ is guaranteed to be within the interval $[r - \epsilon n, r + \epsilon n]$.


following "Space-Efficient Online Computation of Quantile
Summaries", by Greenwald and Khanna.

I'm also interested in whether this is possible with non-integer, non-consecutive moments, so sets of values like $\sum x_i^{-1/2}, \sum x_i^\pi$ are also of interest.

I am more interested in deterministic algorithms than randomized ones.
Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.