weakness is that some of the main results come across as rather simple combinations of existing ideas/results, but on the other hand the simplicity can also be viewed as a strength. I donât find the Experiments section essential, and would have been equally happy to have this as a purely theory paper. But the experiments donât hurt either. My remaining comments are mostly quite minor â I will put a * next to those where I prefer a response, and any other responses are optional: [*] p2: Please justify the claim âoptimal number of measurementsâ - in particular highlighting the k*log(n/k) + 1/eps lower bound from [1] and adding it to Table 1. As far as I know, it is an open problem as to whether the k^{3/2} term is unavoidable in the binary setting - is this correct? (If not, again please include a citation and add to Table 1) - p2: epsilon is used without being defined (and also the phrase âapproximate recoveryâ) - p4: Avoid the uses of the word ânecessaryâ, since these are only sufficient conditions. Similarly, in Lemma 3 the statement âprovided thatâ is strictly speaking incorrect (e.g., m = 0 satisfies the statement given). - The proof of Lemma 1 is a bit confusing, and could be re-worded. - p6: The terminology ârateâ, ârelative distanceâ, and notation H_q(delta) should not be assumed familiar for a NeurIPS audience. - I think the proof of Theorem 10 should be revised. Please give brief explanations for the steps (e.g., the step after qd = (â¦) follows by re-arranging the choice of n, etc.) [*] In fact, I couldnât quite follow the last step â substituting q=O(k/alpha) is clear, but why is the denominator also proportional to alpha/k? (A definition of H_q would have helped here) - Lemma 12: Please emphasize that m is known but x is not â this seems crucial. - For the authorsâ interest, there are some more recent refined bounds on the âfor-eachâ setting such as âLimits on Support Recovery with Probabilistic Models: An Information-Theoretic Frameworkâ and âSparse Classification: A Scalable Discrete Optimization Perspectiveâ, though since the emphasis of this paper is on the âfor-allâ setting, mentioning these is not essential. Very minor comments: - No need for capitalization in âGroup Testingâ - Give a citation when group testing first mentioned on p3 - p3: Remove the word âtypicalâ from âthe typical group testing measurementâ, I think it only increases ambiguity/confusion. - Lemma 1: Is â\cdotâ an inner product? Please make it clear. Also, should it be mx or m^T x inside the sign(.)? - Theorem 8: Rename delta to beta to avoid inconsistency with delta in Theorem 7. Also, is a âfor all dâ statement needed? - Just before Section 4.2, perhaps re-iterate that the constructions for [1] were non-explicit (hence highlighting the value of Theorem 10). - p7: âvery low probabilityâ -> âzero probabilityâ - p7: âThis connection was known previouslyâ -> Add citation - p10: Please give a citation for Pr[sign = sign] = (â¦ cos^-1 formula â¦). === POST-REVIEW COMMENTS: The responses were all as I had assumed them to be when stating my previous score, so naturally my score is unchanged. Overall a good paper, with the main limitation probably being the level of novelty.
- p7: âvery low probabilityâ -> âzero probabilityâ - p7: âThis connection was known previouslyâ -> Add citation - p10: Please give a citation for Pr[sign = sign] = (â¦ cos^-1 formula â¦). === POST-REVIEW COMMENTS: The responses were all as I had assumed them to be when stating my previous score, so naturally my score is unchanged. Overall a good paper, with the main limitation probably being the level of novelty.