NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:2814
Title:Estimating Entropy of Distributions in Constant Space

The reviewers read the authors feedback and realized that the lower bound was actually challenging to obtain. They decided that this paper was worth accepting as it contains a significant amount of novelty in the proposed lower bound. Note that it was noted that the authors didn't fully validate some of the concerns, and it would be useful to take them into consideration in the final camera-ready version of the paper: "For streaming algorithms, time lower bounds are pretty hard and this paper achieve a constant space upper bound (and so it can be said to be tight up to a constant factor in terms of space complexity). How serious is the lower bound thing?" "What is the significance of the logarithmic improvement, where people may just like a suboptimal but simple algorithm which is only off a log factor of another possibly suboptimal but complicated algorithm?"