The paper consider estimating additive, Lipschitz properties of distributions and proposes a new technique based on a piecewise polynomial approximation. The approach is fairly general (in particular it is applicable to asymmetric properties, while PML-type approaches won't be a good fit) and gives near-optimal results in the regime of interest k, n \to \infty. We had a long discussion about this paper. On the positive side: 1. The results are interesting, especially that we get estimators for asymmetric properties and with high-probability guarantees. 2. The techniques are definitely non-trivial, but seem somewhat natural/incremental in light of global polynomial approximation ideas already in the literature. But given that the proofs are non-trivial, it seems useful to have an analysis for local polynomial approximation estimators worked out, and the paper does this with generality. On the negative side: 1. The conceptual main message of the paper seems confused. My sense is that local polynomial approximations is the main message, but the paper spends substantial time on near-linear time, privacy and several other distractions. This makes it much harder to figure out what's going on. 2. There is some overselling/over-claiming going on, as the reviewers have pointed out. Specifically sub-optimal dependencies in the "lower order" terms are largely ignored (the rebuttal provides a compelling answer to this, and I suggest adding it to the paper) and some important prior results are omitted from the discussion. Despite these negatives, the reviewers and I believe the pros outweigh the cons here, so we are recommending acceptance. I strongly encourage the reviewers to do a thorough re-writing of the paper for the camera ready, focusing on the a simple conceptual message.