The paper studies a fundamental problem and provides new lower bounds that come close to matching know upper bounds. The reviewers all strongly support accepting the paper. They also find the techniques used in the paper interesting in their own right. 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.15812) 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.