Before revision:  Our first main result is to estimate the values c_x using roughly \tilde O( q{\varepsilon^2}) samples for general Gibbs distributions and \tilde O( n^2{\varepsilon^2} ) samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors.
After revision:  Our first main result is to estimate the counts c_x using roughly \tilde O( q{\varepsilon^2}) samples for general Gibbs distributions and \tilde O( n^2{\varepsilon^2} ) samples for integer-valued distributions (ignoring some second-order terms and parameters), and we show this is optimal up to logarithmic factors.