{"id":"47907825-07ce-487a-b5df-f5e992532f5c","arxiv_id":"2608.02176","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Hidden partitions can be learned with O(nk log n) PAIR queries in 3 rounds (known k) or O(n|P| log^2 n) in 4 rounds (unknown k), and 2- or 3-round algorithms need Omega(n^{4/3} k^{2/3}) queries.","lead":"Randomized algorithms can learn a hidden partition with near-optimal query counts in only 3–4 rounds, while deterministic algorithms need far more rounds when the number of groups is unknown. The paper proves both new algorithms and matching lower bounds, resolving an open direction from BMS 2025.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unknown-k upper bound unsupported: Theorem 2.10's identity is off by sqrt(log n), and Algorithm 2 can leave ~n^{1-o(1)} unclassified points, making the final round exceed O(nk log^2 n).","rationale":"The reader identified the lower-bound R' condition as the weakest assumption and rated correctness risk low, but the more serious problem is in the unknown-k upper bound. The proof of Theorem 2.10 contains a false equality: the threshold computed from the algorithm's own parameters is 2^{i-1} sqrt(log n), not 2^{i-1}. Because of this missing factor, the set of unclassified points after the penultimate round can be polynomially larger than the proof allows. The equal-cluster example with k = n^{0.9} shows the final all-pairs round alone can cost n^{2-o(1)}, which is not O(nk log^2 n) = n^{1.9+o(1)}. This directly undermines the paper's central claim that randomization gives a 4-round algorithm with near-optimal query complexity when |P| is unknown. It is not a matter of fixing a typo in the pseudocode: the algorithm's sampling rate is too low because of the erroneous factor, and a different design or analysis is needed. The lower-bound proof, while dense, does not appear to have the same issue: the R' sparsity bound is sufficient to keep (a,b) close to uniform, since edges between R and U_i\\R_i do not eliminate the special pair from the candidate set. However, the upper-bound flaw is a stronger reason to withhold acceptance. A revision could potentially repair the algorithm, but the present version's main unknown-k result is unproven.","tokens_in":23529,"tokens_out":61576,"duration_ms":446281,"concrete_test":"Recompute the identity in Theorem 2.10: with \\hat k = 2000 k^* log n and k^* = n/(4^i * 500 log n), verify that sqrt(n log n / \\hat k) = 2^{i-1} sqrt(log n), not 2^{i-1}. Then simulate the equal-cluster instance n = 2^{10^6}, k = n^{0.9}: run Algorithm 2 (first round to find the useful i, then Algorithm 1) and record the size of P' after round 2 and the number of all-pairs queries in the final round. If |P'|^2 >> nk log^2 n, the stated algorithm fails its claimed bound; if the algorithm is modified by removing the log n in the definition of k^*, re-run the same test to check whether the bound is restored.","verdict_should_be":"REJECT","load_bearing_attack":"Load-bearing concern: Theorem 2.10's proof hinges on the identity sqrt(n log n / \\hat k) = 2^{i-1}, but substituting the algorithm's values gives a factor sqrt(log n). Specifically, \\hat k = 2000 k^* log n and k^* = n/(4^i * 500 log n), so \\hat k = n/4^{i-1}, and sqrt(n log n / \\hat k) = 2^{i-1} sqrt(log n), not 2^{i-1}. Hence clusters of size up to ~2^{i-1} sqrt(log n) can remain unclassified after the second round; the proof's claim that P' is contained in \\cup_{i'<i} U_{i'} is false. This is not a constant-factor issue. Take n large with k = n^{0.9} equal clusters of size n^{0.1}. The first useful i is ~0.1 log n, giving \\hat k ~ 4 n^{0.8}; Algorithm 1 then samples m ~ n^{0.9} sqrt(log n) points. Each cluster is missed with probability exp(-m/k) = exp(-O(sqrt(log n))), so the expected unclassified set has size ~ n^{1 - O(1/sqrt(log n))}. The final all-pairs round costs ~ n^{2 - O(1/sqrt(log n))}, which for sufficiently large log n exceeds n^{1.9} = nk and is not O(nk log^2 n). Thus Algorithm 2 as written does not satisfy Theorem 2.6; this requires a substantive correction, not just a typo. The reader's weaker-assumption concern about the lower-bound R' condition is not the most acute issue: the Q1 cap on same-R_i pairs is sufficient to keep (a,b) nearly uniform, but the unknown-k algorithm's query bound is broken by the missing sqrt(log n).","agreement_with_reader":"disagree"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: read this for the known-k results and the deterministic unknown-k separation; the paper's headline unknown-k randomized algorithm (Theorem 2.6 / Algorithm 2) is not supported as written.\n\nThe known-k 3-round algorithm is sound once you fix the pseudocode: Round 2 should query the at-most-k representatives S, not all of R. With that fix, the O(nk log n) whp bound goes through, and the 2-round Omega(n^{4/3} k^{2/3}) lower bound via the DOUBLETON/SINGLETON distribution is clean. The \"at most k parts\" wording in Theorem 3.2 is off by a constant (the distribution has 2k+1 or 2k+2 parts), but scaling k fixes that; it is a textual issue. The deterministic unknown-k results in Section 4 look like a genuine contribution and appear correct.\n\nThe problem is the unknown-k randomized upper bound. Theorem 2.10's proof claims sqrt(n log n / khat) = 2^{i-1}, but substituting khat = 2000 k* log n and k* = n/(4^i * 500 log n) gives 2^{i-1} sqrt(log n). The claimed containment P' subseteq union_{i'<i} U_{i'} is false: clusters of size up to roughly 2^{i-1} sqrt(log n) can remain, and those live in indices up to i + (1/2) log log n. The stress-test's example is on point: k = n^{0.9} equal clusters of size n^{0.1}; the first useful i is about 0.1 log n, khat is about 4 n^{0.8}, R has about n^{0.9} sqrt(log n) points, and each cluster is missed with probability exp(-O(sqrt(log n))), leaving about n^{1-o(1)} unclassified points. The final all-pairs round then costs about n^{2-o(1)}, which is not O(nk log^2 n) since nk = n^{1.9}. And you can't simply multiply khat by log n: that pushes the extra log into the first round's |R|^2 term and loses the bound. This is a load-bearing gap, not a typo. The subset-query corollary inherits it.\n\nThe reader's other flagged issues are minor; this missing sqrt(log n) is the one that matters. Bottom line: the known-k half and the deterministic separation deserve a serious referee. The unknown-k randomized claim needs a real fix or should be withdrawn. I'd send it out given the solid parts, but expect major revision.","headline":"Known-k results and deterministic separation are real, but the unknown-k randomized upper bound has a genuine missing sqrt(log n) factor; Algorithm 2 as written can leave n^{1-o(1)} points unclassified.","tokens_in":24451,"tokens_out":15997,"would_cite":true,"duration_ms":107716,"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":"This paper proves that randomized algorithms can learn a hidden partition of n items in just 3 rounds when the number of parts is known, using O(nk log n) yes/no membership queries, and that 2 rounds still require Ω(n^{4/3} k^{2/3}) queries","keywords":["round complexity","PAIR queries","same-cluster queries","randomized algorithms","partition learning","query complexity","unknown number of clusters","deterministic lower bounds"],"falsifier":"Run the two-round lower-bound distribution with n=10^6 and k=n^{1/2}, have a candidate 2-round algorithm issue o(n^{4/3} k^{2/3}) queries, and measure how often it queries the planted pair (a,b); if the hit probability stays bounded away from 0 over many trials, the claimed indistinguishability would be broken. For the upper bound, implement the 3-round algorithm with k=n^{1/2} and record the actual number of queries in the third round; the paper's lemma says the leftover set has size O(√(nk) log n), so if the observed third-round query count grows faster than O(nk log n) ≈ n^{3/2} log n, the","tokens_in":23415,"feed_emoji":"🎲","tokens_out":11087,"duration_ms":88392,"temperature":0.7,"pith_summary":"The paper addresses how many batches (rounds) of yes/no same-part queries are needed to fully recover a hidden partition of n items while spending nearly the information-theoretic minimum of n times the number of parts queries. Its central claim is that randomization collapses round complexity to a constant: with the number of parts k known, a simple 3-round algorithm learns the partition with O(nk log n) queries with high probability, and no 2-round algorithm—randomized or not—can do better than Ω(n^{4/3} k^{2/3}) queries. When k is unknown, four rounds suffice with O(n|P| log^2 n) queries, while three rounds cannot achieve near-optimal query complexity. The paper also shows that for deterministic algorithms, not knowing k forces Θ(log n/log log n) rounds for near-optimal queries, an exponential gap from the known-k case. A reader should care because in crowdsourced entity resolution and clustering, rounds are wall-clock time: a few parallel batches of questions can recover the partition at almost the same cost as the fully sequential optimum.","feed_headline":"Randomized answers cut partition learning to 3 rounds","feed_subtitle":"Two rounds cost as much as deterministic algorithms; three rounds reach near-optimal query count.","key_machinery":"The central machinery is random sampling as a net: a random subset of O(√(nk) log n) elements hits every part of size at least √(n/k), so one round of all-pairs queries inside that sample exposes the part labels of large clusters. For unknown k, the first round runs the same idea at every scale s=2^i: sample O(s log n) elements, test each against O(n/s) random partners, and count elements receiving exactly one positive answer; the smallest useful scale yields a valid lower bound on |P|. The lower-bound machinery is a planted-pair construction: a 'red' layer R is formed by tagging each item independently with probability l^{−1/3} within k random groups, and one pair (a,b) is drawn uniformly f","core_discovery":"Randomization removes the log-log-round barrier for learning a hidden partition with near-optimal query cost. A 3-round algorithm samples O(√(nk) log n) items, queries all pairs among them, queries each representative against all items, then queries all pairs among the few leftovers; the sample hits every part of size ≥√(n/k), so the leftovers are few. With unknown k, a first round testing scales s by counting items with exactly one positive answer among O(n/s) random partners yields a valid lower bound on |P|, and three more rounds finish with O(n|P| log^2 n) queries. Lower bounds use a random pair (a,b) that differs between two worlds; if no query hits (a,b) the worlds look identical, and","pith_inferences":["Inference: the lower-bound technique suggests a general recipe—when a 2-round algorithm's first round must be spent without knowing the part labels, hard distributions can hide a critical pair inside a sparse layer; this recipe may transfer to other pairwise-query learning problems, such as learning a hidden matching or a graph.","Inference: because the unknown-k algorithm's estimate k* can be far below the true |P|, the paper's approach points toward a two-phase template—estimate a loose scale in round one, then run a known-k routine on the derived bound; this template could be adapted to estimate other distributional parameters before a refine step.","Inference: a testable practical question is how the 3-round and 4-round algorithms behave under noisy or faulty same-cluster answers; the 'exactly one positive answer' test used to estimate k seems likely to be fragile under even a small error rate, and designing a noise-robust constant-round variant is a natural next step.","Inference: the paper leaves a concrete open gap—a 3-round unknown-k algorithm needing Ω(n^{4/3}|P|^{2/3}) queries in some round; closing this gap either positively (matching algorithm) or negatively (stronger lower bound) would pin down the exact round-dependent query tradeoff in the unknown-k regime."],"forward_implications":["Known-k partition learning becomes a constant-round problem: three rounds attain O(nk log n) queries whp, so batch-latency cost no longer forces a log-log-n sequential wait.","Randomization gives no advantage at two rounds: the Ω(n^{4/3} k^{2/3}) lower bound matches the deterministic complexity, so the gap opens only at round three.","Unknown-k learning is also constant-round for randomized algorithms, at the price of one extra round and a log factor: O(n|P| log^2 n) queries in four rounds.","For deterministic algorithms, knowing |P| is exponentially important: without it, near-optimal query cost requires Θ(log n/log log n) rounds rather than Θ(log log n).","The same constant-round randomized algorithms carry over to bounded-size subset queries, using eO(nk/s^2) queries instead of O(nk), shrinking query cost when subset queries are available."],"fun_headline_variants":["Randomness removes log-log round barrier for partition learning","3-round randomized algorithm hits near-optimal query complexity","Randomized queries: constant rounds, near-optimal cost","Unknown partition size? 4 randomized rounds do it","Randomness beats determinism: constant rounds vs log-log"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The lower-bound arguments hinge on the premise that after the first round of queries almost no query lands with both endpoints inside the same hidden subgroup U_i, so the answers reveal essentially nothing about the planted pair (a,b); if an algorithm could concentrate many first-round queries inside individual U_i without knowing the labels, the indistinguishability argument would fail.","fun_headline_variants_meta":{"raw":{"variants":["Randomness removes log-log round barrier for partition learning","3-round randomized algorithm hits near-optimal query complexity","Randomized queries: constant rounds, near-optimal cost","Unknown partition size? 4 randomized rounds do it","Randomness beats determinism: constant rounds vs log-log"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000361,"raw_usage":{"total_tokens":1845,"prompt_tokens":863,"completion_tokens":982,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":904}},"tokens_in":607,"tokens_out":982,"duration_ms":10235,"temperature":1.0,"reasoning_tokens":904,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T12:52:25.337993+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the two-round lower-bound distribution with n=10^6 and k=n^{1/2}, have a candidate 2-round algorithm issue o(n^{4/3} k^{2/3}) queries, and measure how often it queries the planted pair (a,b); if the hit probability stays bounded away from 0 over many trials, the claimed indistinguishability would be broken. For the upper bound, implement the 3-round algorithm with k=n^{1/2} and record the actual number of queries in the third round; the paper's lemma says the leftover set has size O(√(nk) log n), so if the observed third-round query count grows faster than O(nk log n) ≈ n^{3/2} log n, the","supporting_citations":[],"review_version":1}