Reviews: Learning Erdos-Renyi Random Graphs via Edge Detecting Queries

The main contributions are threefold: - An algorithm-independent probabilistic lower bound of the number of non-adaptive tests is given via Fano's inequality (Theorem 1). Under the Bernoulli testing, upper bounds are provided for COMP (Theorem 2) and DD (Theorem 3), and a lower bound is provided for SSS (Theorem 4). These in particular show that DD is asymptotically optimal under the Bernoulli testing when \theta 1/2. Although the three review scores exhibited a relatively large split in the initial round of review, after the authors' rebuttal as well as discussion among the reviewers, all the three reviewers have become positive ratings. I would thus like to recommend acceptance of this paper.