The paper provides strong new lower bounds to an actively studies problem. Three of the reviewers are clearly recommending accepting the paper. Although one of the reviewers has some reservations for the motivation of this line of work, after discussion he's also leaning towards accepting the paper. Added after decisions: During the review process, we noticed that the problem and results in this submission are closely related to those in another submission. After I had written my original metareview, it was further brought to my attention that both of these submissions are on arXiv (the other one is arXiv:2006.16200) and the arXiv versions already acknowledge the parallel work. Now that both papers have been accepted to NeurIPS, I'm asking both sets of authors to include in their final versions a discussion explicitly comparing their results to those in the other paper.