The paper received four reviews. Initially, the scores were borderline but more on the side of accepting. The reviews point out that the paper provides a new style of results on a fundamentally important problem, with interesting techniques. However, one reviewer commented on the result itself being unsurprising; two reviewers were critical of the fact that the result depends on a worst-case input distribution; and some concern was expressed about relation to previous work. The reply from the authors was considered by the reviewers mainly satisfactory, but only partially so regarding the worst-case input distribution. After discussion, some scores were raised and the reviewers are in agreement about recommending accepting the paper.