{"id":"23793ae3-f346-46b7-8aa2-6c5155254f5f","arxiv_id":"2505.05009","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The claimed Θ(n^{1+1/(2^r-1)}k^{1-1/(2^r-1)}) characterization of r-round partition learning holds only for k≥r+2 and is contradicted for k=3, r=2.","lead":"This paper claims a complete round-query tradeoff for learning a hidden k-partition with pairwise same-set queries, plus near-optimal bounds for weak and strong subset queries. The headline interpolation result is false as stated for small k: with k=3 and 2 rounds, a simple O(n) algorithm beats the claimed Ω(n^{4/3}) lower bound.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.2 is false as stated: the proof requires r≤k−2, and k=3,r=2 admits a 2-round 2n−2-query algorithm, contradicting the claimed Ω(n^{4/3}) lower bound.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing gap: the proof of Theorem 1.2 explicitly relies on r≤k−2 in the line defining ℓ, while the theorem is stated for all r≥1. This is not a minor presentation issue, because the k=3,r=2 case is a genuine counterexample to the theorem's conclusion. The upper-bound side is not the problem; Theorem 1.1 gives a valid but loose bound in that regime, so the false part is the claimed matching lower bound. The same hidden restriction propagates into the subset-query lower bounds in Theorems 1.5 and 1.6, although the pairwise counterexample alone suffices to reject the paper's central characterization. No additional independent concern was found beyond the reader's; the manuscript's own text in Section 2.2 confirms the missing assumption, and the counterexample is deterministic and elementary. The reader's REJECT verdict is therefore appropriate and should be kept unchanged.","tokens_in":28163,"tokens_out":5824,"duration_ms":60750,"concrete_test":"Instantiate the claimed lower bound at k=3, r=2, n large. Formally specify the 2-round star-of-stars algorithm: round 1 queries (a,u) for all u≠a; if S={u: answer is no} is nonempty, fix b∈S and in round 2 query (b,v) for all v∈S∖{b}. Verify analytically, or by exhaustive simulation over all 3-partitions for small n, that the algorithm recovers the partition and uses at most 2n−2 queries. Then compare this with the Theorem 1.2 bound Ω(n^{4/3}): since 2n−2=o(n^{4/3}), the lower-bound statement cannot hold for these parameters.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2.2 opens by defining ℓ=⌊(k−3)/(r−1)⌋ and says it satisfies ℓ≥1 because r≤k−2, but no such assumption appears in Theorem 1.2, which claims to hold for all r≥1. When k=3 and r=2, ℓ=0, so the repeated-Turán construction cannot even start; the conclusion is also concretely false. A deterministic 2-round algorithm can learn any 3-partition with at most 2n−2 pairwise queries: round 1 queries a fixed root a against all other elements; letting S be the elements answered \"no\", round 2 queries a fixed b∈S against every element of S. This reveals whether S is empty, one class, or split into two classes, and the total number of queries is at most (n−1)+(|S|−1)≤2n−2. For n large this is O(n), while Theorem 1.2 with k=3,r=2 promises Ω(n^{4/3}). Thus the abstract's 'complete characterization' Θ(n^{1+1/(2^r−1)}k^{1−1/(2^r−1)}) for every constant r is an overstatement. At minimum the theorem requires the qualification r≤k−2, and the small-k regime needs a separate statement; as written, the central lower bound is unsound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies exact reconstruction of an unknown partition of n elements into at most k sets from membership-style queries. For pairwise same-set queries it claims a complete round-query tradeoff: for every constant r, the deterministic query complexity is Θ(n^{1+1/(2^r−1)} k^{1−1/(2^r−1)}), together with an O(log log n)-round algorithm attaining the optimal O(nk) query complexity. It then treats weak subset queries (the number of classes intersected) and strong subset queries (the full induced partition) under a query-size bound s, claiming nearly matching upper and lower bounds for non-adaptive and r-round algorithms. The main lower bound is proved through repeated applications of Turán's theorem and a 'carving lemma'; the upper bound is a recursive divide-and-conquer scheme. The subset-query sections include a non-adaptive weak-query algorithm claimed to resolve an open question of BLMS24. The paper does not include code or machine-checked proofs.","tokens_in":28464,"tokens_out":13222,"duration_ms":131810,"significance":"If correct, the pairwise round-query characterization would be a substantial contribution, and the weak-versus-strong subset-query comparison is conceptually interesting. The recursive algorithm of Theorem 1.1 and the non-adaptive weak subset query construction of Section 4 are nontrivial and appear internally coherent. However, the central lower bound is false as stated: the proof requires an unstated condition r ≤ k−2, and there is an elementary counterexample for k=3 and r=2. Because Theorems 1.5 and 1.6 inherit the pairwise lower bound, the advertised characterization cannot be accepted.","major_comments":[{"comment":"Theorem 1.2 is false as stated. The proof defines ℓ = ⌊(k−3)/(r−1)⌋ and asserts 'ℓ≥1 since r≤k−2 by assumption,' but Theorem 1.2 and the abstract claim the bound for all r≥1 and contain no such restriction. For k=3 and r=2, ℓ=0 and the repeated-Turán construction cannot start; the conclusion is also concretely false. A deterministic 2-round algorithm queries a fixed root a against all other n−1 elements, then, if the set S of 'no' answers is nonempty, queries a fixed b∈S against every other element of S. This uses at most (n−1)+(|S|−1) ≤ 2n−2 pairwise queries and exactly recovers any partition into at most 3 sets, contradicting the asserted Ω(n^{4/3}) lower bound for k=3, r=2. Since Theorem 1.2 is the paper's central result, the abstract's 'complete characterization' is unsupported.","section":"2.2 (definition of ℓ; proof of Theorem 1.2)"},{"comment":"The defect is not confined to k=3, r=2. For any constant k≥4 and r=k−1, the known (k−1)-round fully adaptive algorithm of [RS07] uses O(nk)=O(n) queries, whereas the formula in Theorem 1.2 gives Ω(n^{1+1/(2^{k−1}−1)}), which is ω(n). For example, k=4 and r=3 would claim Ω(n^{8/7}) although a 3-round O(n)-query algorithm exists. Thus the lower bound cannot be repaired merely by adding the condition r≤k−2 to Theorem 1.2; the claimed smooth interpolation for all constant r would require a separate, substantially weaker statement in the saturated regime r≥k−2.","section":"Theorem 1.2 and Section 1.1.1"},{"comment":"The subset-query lower bounds inherit the same false premise. Section 1.1.2 derives the lower bounds for strong subset queries from the pairwise lower bound and states that Theorem 1.2 'extends in the same fashion'; Theorems 1.5 and 1.6 consequently quantify over all r, k, and s. The k=3, r=2 counterexample above uses only queries of size 2, so it also contradicts those subset-query lower bounds (for both weak and strong oracles) in the regime where the expression max{(1/r)(1/s²)n^{1+1/(2^r−1)}k^{1−1/(2^r−1)}, n} is dominated by the n^{4/3}/s² term, for example when s=2. Hence the claimed tight subset-query lower bounds are not established.","section":"Section 1.1.2; Theorems 1.5 and 1.6"}],"minor_comments":[{"comment":"The text writes 'since S = S1 ⊔ ... ⊔ Sk where each Si is an independent set,' but the construction produces only ℓ independent sets, so the disjoint union should be indexed by ℓ, not by k.","section":"2.2 (final paragraph)"},{"comment":"The pseudocode recursively calls 'LR-WeakSubsetQuery(R,s′,r−1)', but Algorithm 5 and its proof concern strong subset queries and the induction is for LR-StrongSubsetQuery; this should be corrected.","section":"Algorithm 5, line 13"},{"comment":"The symbol K is used both for the collection of known sets and for its union, which makes the statement of Lemma 4.2 ambiguous; the intended distinction should be made explicit.","section":"Lemma 4.2 and Algorithm 3"}],"recommendation":"reject","confidential_remarks":"The central theorem is contradicted by a simple deterministic algorithm, and the unstated assumption r≤k−2 is visible at the very point where the lower-bound construction begins. I would not recommend further review until the main lower-bound claims are reformulated and the subset-query consequences are re-derived. The upper-bound portions may be salvageable, but the advertised results need substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read this one for the subset-query half and for the clean recursive upper bound. The headline lower-bound characterization, as written, is wrong. Section 2.2 defines ℓ = ⌊(k−3)/(r−1)⌋ and says it satisfies ℓ≥1 because r≤k−2 by assumption. That assumption never appears in Theorem 1.2, which claims all r≥1. And the statement is not just missing a condition; it is concretely false. For k=3, r=2, a deterministic algorithm can learn any 3-partition with at most 2n−2 pairwise queries: query a fixed root against everyone, then query one element from the 'no' set against the rest of that set. That is O(n), while the theorem promises Ω(n^{4/3}). So the abstract's 'complete characterization' overclaims.\n\nThe paper earns credit elsewhere. Theorem 1.1's r-round recursion is simple and gives the claimed interpolation, and the O(log log n)-round O(nk) algorithm is a real improvement over the prior k−1 rounds. The non-adaptive weak subset query algorithm matching the strong-query bound Θ(n^2/s^2) up to logs for s≤√n is the most interesting result in the paper and appears technically sound; it resolves an open question from BLMS24. The strong-query matching bounds and the r-round subset-query extensions are also coherent.\n\nThe soft spot is concentrated in Theorem 1.2. The Turán/Carving-Lemma lower-bound machinery is novel and likely correct for k ≥ r+2, but the paper needs to state that condition, handle the small-k regime separately, and fix the abstract. Until then, the central theorem is unsound. Also check the proof of Lemma 2.4: the inequality chain uses assumptions on |Q1∪...∪Qt| and n>cℓ; those are fine, but the missing condition propagates. The subset-query lower bounds inherit the pair lower bound, so they inherit the qualification too.\n\nWho is this for? Anyone working on query-based clustering or group testing will want the subset-query results; the faulty Theorem 1.2 is a cautionary tale about boundary cases in round-complexity lower bounds. Worth a serious referee, but the referee should demand the repair before acceptance. I would not cite the main characterization until it is fixed; I would cite the subset-query and upper-bound parts.","headline":"Theorem 1.2 is false as stated: the proof needs r ≤ k−2, and a simple 2-round 2n−2-query algorithm for k=3 refutes the claimed Ω(n^{4/3}), but the subset-query results and the recursive upper bound are real and worth a careful referee.","tokens_in":28974,"tokens_out":2993,"would_cite":false,"duration_ms":28639,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For any constant number of rounds r, k-partition learning requires and admits $\\Theta(n^{1+1/(2^r-1)}k^{1-1/(2^r-1)})$ same-set queries; $O(\\log\\log n)$ rounds already attain the optimal $\\Theta(nk)$.","keywords":["partition learning","same-set queries","round complexity","query complexity","adaptive algorithms","subset queries","Turán's theorem","crowdsourced clustering"],"falsifier":"Implement the two-round algorithm for $k=3$: in round one, query a fixed element $u$ against every other element; in round two, pick the first element $w$ not sharing $u$'s class and query $w$ against every remaining element. It recovers any partition into at most three sets with fewer than $2n$ queries, directly contradicting the $\\Omega(n^{4/3})$ lower bound that Theorem 1.2 would give for $r=2$, $k=3$.","tokens_in":27955,"feed_emoji":"🧩","tokens_out":10381,"duration_ms":89087,"temperature":0.7,"pith_summary":"This paper fixes the exact cost of learning an unknown partition of $n$ items into at most $k$ groups when queries are batched into $r$ parallel rounds and each query asks whether two items lie in the same group. For every constant $r$, the deterministic query complexity is $\\Theta(n^{1+1/(2^r-1)}k^{1-1/(2^r-1)})$, a formula that slides from the known $\\Theta(n^2)$ non-adaptive bound at $r=1$ to the known $\\Theta(nk)$ fully adaptive bound as $r$ grows. The paper also shows that $O(\\log\\log n)$ rounds are enough to reach the optimal $O(nk)$ queries, a double-exponential reduction in adaptivity over the earlier $k-1$-round algorithm. For larger subset queries, the same machinery gives nearly tight bounds for weak queries (which report how many groups a set touches) and strong queries (which return the full restricted partition); up to logarithmic factors, weak queries match strong queries whenever the allowed query size is at most $\\sqrt{n}$.","feed_headline":"Log-log n rounds hit the optimal partition-learning query cost","feed_subtitle":"A new formula pins the deterministic cost of same-set queries at every adaptivity level, from n^2 down to nk.","key_machinery":"The load-bearing object is the round-dependent exponent $\\varepsilon(r)=1/(2^r-1)$, which appears in both the query-count formula and the recursion. The algorithm splits $U$ into about $(n/k)^{1-\\varepsilon(r)}$ blocks of size $n^{\\varepsilon(r)}k^{1-\\varepsilon(r)}$, queries all pairs inside each block, forms a representative set $R$, and recurses with $r-1$ rounds; the identities $1+\\varepsilon(r)=(1-\\varepsilon(r))(1+\\varepsilon(r-1))$ and $1-\\varepsilon(r)=\\varepsilon(r)(1+\\varepsilon(r-1))+(1-\\varepsilon(r-1))$ make the costs of the two levels add exactly. The lower bound is carried by Tur\\'an's theorem, which guarantees an independent set of size at least $n/(1+d)$ in any graph of average degree $d$, and by a Carving Lemma that refreshes a family of disjoint independent sets round after round while keeping the oracle answers on earlier queries unchanged.","core_discovery":"The central claim is a complete round-versus-query trade-off for deterministic partition learning: an $r$-round algorithm needs and suffices with $\\Theta(n^{1+1/(2^r-1)}k^{1-1/(2^r-1)})$ pairwise same-set queries for every constant $r$. The matching upper bound uses a recursive split-and-recurse scheme whose exponents telescope via the identity $(1-\\varepsilon(r))(1+\\varepsilon(r-1))=1+\\varepsilon(r)$ with $\\varepsilon(r)=1/(2^r-1)$. The lower bound models the first $r-1$ rounds of queries as edges of a graph, applies Tur\\'an's theorem repeatedly to carve disjoint independent sets, and turns those sets into a pair of hard partitions that the final round cannot distinguish unless it queries every remaining pair inside the surviving region. Beyond pairwise queries, the paper shows non-adaptive weak subset queries achieve $\\tilde{\\Theta}(n^2/s^2)$ for query size $s\\le\\sqrt{n}$, matching the strong-query bound up to log factors.","pith_inferences":["The stated 'for all $r\\ge1$' lower bound is not supported by the proof when $r>k-2$; the $k=3,r=2$ counterexample shows the complete characterization found here holds in the regime $r\\le k-2$, and a different argument will be needed for rounds comparable to $k$.","The recursive exponent identity provides a general design template: split, learn pieces non-adaptively, and recurse on representatives. It is already applied in the paper to subset queries, and it should transfer to other query models whose non-adaptive cost is $n^{1+\\theta}$, yielding $r$-round costs of the form $n^{1+\\theta/(2^{r-1})}$.","Because the randomized lower bound is explicitly left open, a plausible next step is a randomized separation: for example, a 2-round randomized algorithm might learn 3-partitions with $o(n^{4/3})$ queries by sampling a small set of representatives, which would show randomness helps in the low-round regime.","The equivalence of weak and strong subset queries up to $s=\\sqrt{n}$ is derived in a noiseless setting; testing whether it persists under noisy or faulty oracles would tell whether the communication savings of weak queries survive in realistic crowdsourcing pipelines."],"forward_implications":["For every constant $r$, the deterministic $r$-round query complexity of $k$-partition learning is now exactly known, so a designer can read off how many queries a given level of parallelism costs.","Because $O(\\log\\log n)$ rounds already attain $O(nk)$ queries, applications that can batch queries (crowdsourced clustering, entity resolution) can have near-fully-adaptive performance with almost no adaptivity.","Non-adaptive weak subset queries cost $\\tilde{\\Theta}(n^2/s^2)$ for $s\\le\\sqrt{n}$, matching strong subset queries up to logarithmic factors, so query oracles that only count touched groups are essentially as powerful as oracles that reveal the full local partition in this regime.","With query size $s=O(\\sqrt{k})$ and $O(\\log\\log n)$ rounds, partition learning uses $\\tilde{O}(n)$ weak subset queries, a near-linear query count obtained previously only with query size $O(k)$ and $O(\\log k)$ rounds.","The Tur\\'an-based lower-bound technique supplies a reusable method for proving round-sensitive lower bounds for graph and partition reconstruction problems beyond the specific pair-query model."],"supporting_citations":[{"why":"Supplies the connected-components/partition-learning formulation and the baseline $k-1$-round $O(nk)$ algorithm that the new recursion improves.","marker":"[RS07]"},{"why":"Establishes the $\\Omega(n^2)$ non-adaptive lower bound and the adaptive $\\Theta(nk)$ framework that the round interpolation must match.","marker":"[MS17a]"},{"why":"Gives the tight fully-adaptive $\\Omega(nk)$ query lower bound, the endpoint of the new trade-off curve.","marker":"[LM22]"},{"why":"Provides the non-adaptive subset-query upper bounds and poses the open question on $\\tilde{\\Theta}(n^2/s^2)$ weak-query complexity that Theorem 4.1 resolves.","marker":"[BLMS24]"},{"why":"Supplies the adaptive $O(n)$-query algorithm using rank queries and the comparison point for query-size-bounded weak subset queries.","marker":"[CL24]"}],"fun_headline_variants":["Round-query tradeoff fully pinned for partition learning","Optimal same-set queries at every round count, from n^2 to nk","O(log log n) rounds reach optimal nk query cost","Subset queries: weak matches strong non-adaptively up to logs","Complete r-round tradeoff for partition learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound proof in Section 2.2 assumes $r\\le k-2$, needing $\\ell=\\lfloor(k-3)/(r-1)\\rfloor\\ge1$ disjoint independent sets to build its hard partition, and the theorem statement as written omits this restriction; when it fails the bound is not merely unproved but false, since a two-round algorithm using about $2n$ queries learns any 3-partition.","fun_headline_variants_meta":{"raw":{"variants":["Round-query tradeoff fully pinned for partition learning","Optimal same-set queries at every round count, from n^2 to nk","O(log log n) rounds reach optimal nk query cost","Subset queries: weak matches strong non-adaptively up to logs","Complete r-round tradeoff for partition learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001582,"raw_usage":{"total_tokens":6415,"prompt_tokens":1154,"completion_tokens":5261,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":770,"completion_tokens_details":{"reasoning_tokens":5174}},"tokens_in":770,"tokens_out":5261,"duration_ms":35884,"temperature":1.0,"reasoning_tokens":5174,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:17:34.832777+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the two-round algorithm for $k=3$: in round one, query a fixed element $u$ against every other element; in round two, pick the first element $w$ not sharing $u$'s class and query $w$ against every remaining element. It recovers any partition into at most three sets with fewer than $2n$ queries, directly contradicting the $\\Omega(n^{4/3})$ lower bound that Theorem 1.2 would give for $r=2$, $k=3$.","supporting_citations":[],"review_version":1}