{"id":"0ca9267d-0677-4287-b7de-7e7fc84be7f9","arxiv_id":"2412.17751","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A greedy adaptive algorithm identifies the infected subset in O(H(X)+mu) expected tests for any correlated infection distribution over a hypergraph, with extensions to semi-non-adaptive and noisy settings.","lead":"The paper gives group-testing algorithms that exploit arbitrary correlations among people, modeled by a hypergraph whose edges carry probabilities. It proves the needed number of tests is roughly the information content of the infection distribution plus the expected number of infected people, and extends this to pre-scheduled and noisy tests.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the noiseless adaptive O(H+u) bound is internally sound; remaining caveats are the exact-knowledge-of-D modeling assumption and broad comparison claims, not fatal flaws.","rationale":"The reader's conditional verdict identifies as the weakest assumption the requirement of exactly one infected hyperedge and exact knowledge of D. The exact-knowledge requirement is real but standard for probabilistic group testing with priors and is not a flaw in the theorem as stated. The 'multiple disjoint sets' part of the reader's concern is not actually outside the model: an arbitrary joint distribution P(S) over subsets is represented by taking each subset S in the support as a single hyperedge, and exactly one such hyperedge is realized. Thus the posterior removal rule remains valid for arbitrary correlation. The noiseless adaptive proof checks out: Lemma 4.3 correctly computes the posterior via edge removal and renormalization; Lemma 4.4 correctly counts informative tests against the entropy of the edge distribution; Lemma 4.8 correctly bounds Stage-2 individual tests by the posterior expected infection count; and Corollary 4.10 plus Theorem 4.11 correctly convert a stochastic upper bound on the target edge size into an O(H+u) or O(H+µ/epsilon) bound. The remaining issues are the abstract's broad 'recovers or improves all prior results' claim, which is not fully supported because Section 5 comparisons sometimes require concentration and ignore constants, and the noisy-testing analysis, which is informal but does not affect the noiseless central claim. These justify the reader's conditional verdict but do not amount to a load-bearing objection to the main algorithmic guarantee.","tokens_in":48652,"tokens_out":35400,"duration_ms":354931,"concrete_test":"Independently re-derive and numerically verify Theorem 4.11 on all hypergraphs with n<=4 and all rational distributions D: simulate the modified Algorithm 1 and check that for every epsilon the expected test count is at most 2/log(3/2)H(X)+2µ/epsilon and the success probability is at least 1-epsilon; also run one misspecified-D variant to document the exact-prior requirement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After reviewing the noiseless adaptive analysis, I do not find a load-bearing flaw in the central claim. Lemma 4.3 is a correct Bayesian update given the model's definition that exactly one edge e~D is realized; arbitrary joint distributions over subsets are represented by taking the support as the hyperedge set, so 'multiple disjoint infected sets' are not outside the model. The O(H+u) and O(H+µ/epsilon) bounds in Theorem 4.11 and Corollary 4.12 follow from the informative-test counting in Lemma 4.4 and the Stage-2 individual-test bound in Lemma 4.8. The substantive caveats are (i) D must be known exactly, because a misspecified prior invalidates the posterior update in Definition 3.2, and (ii) the abstract's 'improves all previously known results' overstates the comparisons in Section 5, which rely on concentration or stochastic upper bounds. These are presentation and modeling caveats, not internal inconsistencies in the central algorithmic argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a hypergraph-based model for group testing under arbitrary statistical correlation: a hyperedge (a subset of nodes) is sampled from a known distribution D, and the infected set is exactly that hyperedge. The authors propose an adaptive greedy algorithm that maintains a posterior over hyperedges, performs informative tests that remove a constant fraction of the probability mass, and then tests remaining uncertain nodes individually. They upper bound the expected number of tests by O(H(X)+µ) under edge-size assumptions and by O(H(X)+u) when a stochastic upper bound u on the infected-set size is known (Theorem 4.11 and Corollary 4.12). They claim to recover or improve prior correlated group testing results, provide examples showing when entropy is a loose lower bound, establish order optimality for dense and sparse random d-regular hypergraphs, and extend the framework to semi-non-adaptive and noisy group testing.","tokens_in":48861,"tokens_out":18379,"duration_ms":183179,"significance":"If the main results hold, the paper is a valuable unifying treatment of group testing with correlated infection patterns. The adaptive noiseless analysis is attractive: Lemma 4.3 derives the correct Bayes update for the single-edge model, Lemma 4.4 gives a clean informative-test counting argument, and Corollary 4.12 provides a bound depending only on H(X) and a stochastic size bound u. The lower-bound examples in Section 6 are concrete and informative, and the random-hypergraph optimality results in Section 6.4 are nontrivial. The main caveats are the exact-knowledge assumption on D, the informal nature of the noisy-section analysis, and some overstated comparison claims in Section 5 and the abstract.","major_comments":[{"comment":"The lower bound L ≥ (1−ε)H(X) is false as stated. Fano's inequality gives L ≥ H(X) − h(ε) − ε log(|E|−1), and the omitted terms can be non-negligible. A concrete counterexample: take three singleton hyperedges with uniform probabilities, so H(X)=log 3. One test of the first node recovers the edge with error probability 1/6 (if the test is negative, output the second edge; error occurs only when the third edge is true). Thus L=1 and ε=1/6, but (1−ε)H(X)=(5/6)log 3 > 1, contradicting the theorem. Since Theorem 2.2 is used in Section 6 to support order-optimality claims, the statement needs to be corrected, for example by adding the standard entropy-error terms, or by proving the bound only under conditions where those terms are o(H(X)) when ε→0.","section":"§2.3, Theorem 2.2"},{"comment":"The proof does not provide a valid stopping-time argument for the number of line-6 tests. The displayed lower bound q(e*) ≥ p(e*) c'^M cannot be used to conclude that the algorithm 'must have fewer than' M tests, because q(e*) is a probability and can never exceed 1; a lower bound exceeding 1 only indicates that the bound is too crude. Moreover, in the noisy modification no edge is ever eliminated and the algorithm does not stop when q(e*) reaches 1; the transition from line 6 to Stage 2 is governed by the greedy condition c ≤ w(S) ≤ 1−c. A rigorous bound on the random number of line-6 tests is needed, for example via a potential function or a martingale argument that couples the posterior growth with the actual stopping rule. As written, the proof does not establish the first term of Theorem 8.1's bound.","section":"§8, Theorem 8.1 proof, paragraph 'Upper bound'"},{"comment":"The claimed improvement over [NSG+21a] relies on the assertion that if F≫1 and M≫1, then the number of infections is concentrated around its mean, so that Corollary 4.12 applies with u=O(µ). This is not true for arbitrary q and p in the family model: for example, with q=O(F^{-2}), M=F, and p=1/2, the mean number of infected nodes is O(1) and the fluctuations are not vanishing relative to the mean, so a stochastic upper bound u=O(µ) need not hold. The comparison should be stated under explicit concentration conditions, and the abstract's claim to 'recover or improve all previously known results' should be correspondingly qualified.","section":"§5, comparison with [NSG+21a]"}],"minor_comments":[{"comment":"There is a typo: 'proabilities' should be 'probabilities'.","section":"§3.2 after Figure 1"},{"comment":"'Figure 1 show' should be 'Figure 1 shows'.","section":"§2, Figure 1 caption"},{"comment":"The error-probability expression '1 − O(1/ min(n, g(n))' is missing a closing parenthesis; it should read '1 − O(1/min(n, g(n)))'.","section":"§8, Theorem 8.1 statement"},{"comment":"The condition c > 1 − (1−δ)^{1−δ}δ^δ together with c < 1/2 restricts δ away from 1/2; this limitation should be stated explicitly, since the theorem does not cover noise levels near the symmetric capacity limit.","section":"§8, condition in Theorem 8.1"},{"comment":"The statement that Theorem 4.9 'slightly improves' the [GLS22] bound should be phrased as a comparison for the probabilistic uniform-edge model, not as an improvement of the worst-case combinatorial bound in [GLS22], since the two settings are not identical.","section":"§5, comparison with [GLS22]"}],"recommendation":"major_revision","confidential_remarks":"The noiseless adaptive core of the paper is likely correct and is the strongest part. The main barriers to acceptance are (i) the entropy lower bound in Theorem 2.2 is false as stated and should be corrected, (ii) the noisy-section proof in Theorem 8.1 needs a genuine stopping-time analysis rather than the informal posterior-crossing argument, and (iii) the abstract overstates the comparison results. These are fixable, but the required work is substantial enough to warrant a major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious look from anyone working on probabilistic group testing with correlation. The core move is clean: represent an arbitrary joint distribution over infected subsets as a probability distribution on hyperedges, then run a greedy adaptive algorithm that tests complements of sets whose edge-weight is bounded away from 0 and 1. The two-stage design is natural, and the main noiseless bound, O(H(X)+mu) tests in expectation (Theorem 4.11, Corollary 4.12), is well argued. Lemma 4.3 is the key step and it is correct: conditioning on a test outcome really is just removing a set of edges and renormalizing, and the informative-test counting in Lemma 4.4 gives an honest entropy bound.\n\nThe lower-bound examples in Section 6 are genuinely useful, not filler. Example 6.1 showing entropy can be loose by a factor of n/log n, and Examples 6.6 and 6.7 showing mu is not always a lower bound, clarify what the bound can and cannot capture. The random-hypergraph optimality analysis in Section 6.4 is careful and even flags where the algorithm is not tight. I also appreciate that the paper explicitly gives examples where its own analysis is loose.\n\nThe soft spots are real but not fatal. The abstract's claim of 'recovers or improves upon all previously known results' is too strong. The Section 5 comparisons are conditional on concentration or large parameter regimes, which the body does state, but the abstract overstates. The bigger modeling caveat is that the algorithm needs exact knowledge of D; if the prior is misspecified, the posterior update in Definition 3.2 no longer computes the true posterior and the guarantee fails. That assumption should be front and center. The noisy section (8) is the weakest: the random number of line-6 tests is handled informally, and the convolutions of Chernoff bounds are sketched rather than fully formalized. The SNAGT proof in Section 7 / Appendix C is similarly prose-heavy. All of this is fixable.\n\nWho is this for? Information theorists and algorithms people working on group testing with correlated priors. The noiseless adaptive result and the lower-bound examples deserve referee time. I would encourage the editor to send it out, but with concrete requests: soften the abstract, state the exact-D assumption prominently, and tighten the noisy and SNAGT analyses.","headline":"A sound, genuinely useful generalization of correlated group testing; the central O(H+mu) bound is well supported, but the abstract overclaims and the exact-knowledge-of-D assumption deserves more prominence.","tokens_in":49356,"tokens_out":1460,"would_cite":true,"duration_ms":16561,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","05C65"],"pacs":[],"model":"deepseek-v4-flash","headline":"A greedy adaptive algorithm identifies the infected hyperedge in O(H(X)+μ) tests in expectation, and the bound is order-optimal for several random hypergraph families.","keywords":["group testing","correlated infections","hypergraphs","adaptive algorithms","entropy bounds","posterior update","noisy group testing","semi-non-adaptive group testing"],"falsifier":"Allow the infected set to be a union of two disjoint hyperedges drawn independently while keeping everything else identical. Then the key equivalence fails: a positive test of V \\ S no longer implies the target edge lies outside E(S), so the deletion rule can remove a truly infected edge; running Algorithm 1 on this two-infection variant and observing the wrong edge survive would isolate exactly which assumption the entropy-based guarantee rests on.","tokens_in":48479,"feed_emoji":"🧪","tokens_out":11776,"duration_ms":109139,"temperature":0.7,"pith_summary":"Most group-testing theory assumes each person's infection status is independent of others, but real outbreaks and network faults are correlated. This paper tries to remove that assumption entirely: it models every subset that could be the infected set as a hyperedge carrying a known probability, then asks how many group tests are needed to identify the true subset. The paper's central claim is that a greedy adaptive algorithm—test a group whose complement contains the right amount of probability mass, then update beliefs by discarding ruled-out subsets—finds the infected set in O(H(X)+μ) expected tests, where H(X) is the entropy of the infection distribution and μ is the average number of infected people. It further shows that this bound recovers or improves all previously known correlated group-testing bounds, and that it is order-optimal for several families of random hypergraphs. If the claim is right, the same testing recipe works for any correlated setting in which a joint distribution over infected subsets is available.","feed_headline":"Correlated group test count is O(entropy plus mean infections)","feed_subtitle":"Greedy adaptive testing updates beliefs after every result, matching known lower bounds in many regimes.","key_machinery":"The load-bearing object is the edge-weight function w(S), the total posterior probability of hyperedges fully contained in S. Because a test of V \\ S is positive exactly when the target hyperedge lies outside E(S), either outcome lets the algorithm delete a known probability block—E(S) on a positive result, its complement on a negative result. Lemma 4.3 shows that deleting the ruled-out block and scaling the remaining probabilities is the true posterior update, which is what makes the greedy removal rule valid. The algorithm greedily shrinks S until c ≤ w(S) ≤ 1-c, so every informative test removes a constant fraction of the remaining mass and the elimination count is bounded by entropy.","core_discovery":"Under the model, exactly one hyperedge e is drawn from a known distribution D and all nodes in e are infected. Algorithm 1 repeatedly builds a candidate set S of still-possible nodes, tests its complement, and updates the posterior by deleting the ruled-out edge class and renormalizing the rest; Lemma 4.3 proves this deletion-and-scale step is the exact Bayesian update. Each informative test removes at least a constant fraction c of the remaining probability mass, so the expected number of such tests is at most H(X)/log(1/(1-c)). When no such test remains, the surviving nodes are almost surely infected and individual testing costs at most the posterior expected infection count divided by 1-2c, giving the O(H(X)+u) guarantee when u stochastically upper-bounds the infected-edge size. The paper also proves the (1-ε)H(X) information-theoretic lower bound, and it gives families of hypergraphs where the algorithm is order-optimal and others where entropy is not a tight lower bound.","pith_inferences":["Beyond the paper: because the algorithm only needs a stochastic upper bound u rather than the exact mean, it is robust to approximate estimates of μ; one could run it with a plug-in empirical distribution and expect graceful degradation, though the paper does not quantify the misspecification cost.","Beyond the paper: the posterior-removal rule is a general Bayesian search primitive, so the same O(H+u) analysis should carry over to other sequential identification problems with one hidden object and noisy subset queries, not just infection testing.","Beyond the paper: the n/log n adaptive-to-non-adaptive gap suggests that finding hypergraph families where non-adaptive designs match adaptive performance would be the natural next target; the paper leaves this open.","Beyond the paper: the noisy-testing bound improves on simple repetition by updating posteriors with the flip probability, implying that in high-entropy regimes the noise penalty is additive rather than multiplicative; a direct comparison with majority-vote repetition is given in Remark 8.2."],"forward_implications":["Independent probabilistic group testing is recovered as a special case: with concentrated infection counts, Algorithm 1 matches the prior O(H(X)+μ) adaptive bound up to constants.","For the family-community model of [NSG+21a], the expected test count drops from O(Fq(log F + M) + nqp log n) to O(F(h2(q) - w h2((1-q)/w)) + nq(h2(p)+p)) in the large-F, large-n regime.","For uniform set-systems with |E| candidate subsets of size d, the algorithm uses O(log |E| + d) tests, improving the earlier O(log |E| + d log^2 d) guarantee.","The entropy H(X) is not a tight lower bound under correlation: some n-node hypergraphs have H(X)=O(log n) while any algorithm with constant success probability needs Ω(n) tests.","On dense d-regular random hypergraphs the algorithm is order-optimal, and a modified version is order-optimal on sparse d-regular random hypergraphs, using O(H(X)) tests when d is o(n)."],"supporting_citations":[{"why":"Supplies the hypergraph set-system model of candidate infected subsets that this paper augments with probabilities over edges.","marker":"[GLS22]"},{"why":"Gives the entropy lower bound and the O(μ+H(X)) adaptive guarantee for independent probabilistic group testing that this paper generalizes.","marker":"[LCH+14]"},{"why":"Provides the family-community infection model used as a comparison instance where the new algorithm improves the prior test count.","marker":"[NSG+21a]"},{"why":"Provides the stochastic block infection model whose entropy and mean infection count are used to show order-optimality under weak conditions.","marker":"[AC ¨O23]"},{"why":"Gives the edge-faulty graph correlation model translated into the hypergraph-plus-distribution formalism in Section 2.2.","marker":"[NKC+22]"},{"why":"Gives the single-infected-component graph model also translated into the paper's hypergraph formalism.","marker":"[AU23]"}],"fun_headline_variants":["Hypergraph test algorithm hits entropy bound for correlated infections","Adaptive group testing tames correlations with greedy Bayesian updates","Correlated group testing: O(entropy + mean infections) achieved","New greedy algorithm matches lower bound for correlated group testing","Greedy adaptive tests achieve O(H + expected infections) for correlations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole guarantee depends on the infection being exactly one hyperedge drawn from a probability distribution the algorithm knows exactly; if several disjoint subsets can be infected at once, or if the supplied distribution is wrong, the rule that discards ruled-out subsets no longer yields correct updated odds and the O(H+u) bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Hypergraph test algorithm hits entropy bound for correlated infections","Adaptive group testing tames correlations with greedy Bayesian updates","Correlated group testing: O(entropy + mean infections) achieved","New greedy algorithm matches lower bound for correlated group testing","Greedy adaptive tests achieve O(H + expected infections) for correlations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000626,"raw_usage":{"total_tokens":2904,"prompt_tokens":961,"completion_tokens":1943,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":1858}},"tokens_in":577,"tokens_out":1943,"duration_ms":13570,"temperature":1.0,"reasoning_tokens":1858,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:13:38.942237+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Allow the infected set to be a union of two disjoint hyperedges drawn independently while keeping everything else identical. Then the key equivalence fails: a positive test of V \\ S no longer implies the target edge lies outside E(S), so the deletion rule can remove a truly infected edge; running Algorithm 1 on this two-infection variant and observing the wrong edge survive would isolate exactly which assumption the entropy-based guarantee rests on.","supporting_citations":[],"review_version":1}