Pith. sign in

REVIEW 3 major objections 3 minor 51 references

Learning Partitions with Optimal Query and Round Complexities

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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)$.

desk verdict 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. read the letter →

arxiv 2505.05009 v1 pith:LTGPXKGN submitted 2025-05-08 cs.DS cs.ITcs.LGmath.IT

Hadley Black , Arya Mazumdar , Barna Saha This is my paper · ORCID
classification cs.DScs.ITcs.LGmath.IT
keywords partitionlearningsame-setqueriesroundcomplexityqueryadaptivealgorithmssubsetTurán'stheoremcrowdsourcedclustering
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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}$.

What carries the argument

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.

What would settle it

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$.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

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.

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 (3)
  1. [2.2 (definition of ℓ; proof of Theorem 1.2)] 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.
  2. [Theorem 1.2 and Section 1.1.1] 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.
  3. [Section 1.1.2; Theorems 1.5 and 1.6] 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.
minor comments (3)
  1. [2.2 (final paragraph)] 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.
  2. [Algorithm 5, line 13] 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.
  3. [Lemma 4.2 and Algorithm 3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's bounds are derived from self-contained Turán/Carving arguments and independent benchmarks; the flagged r≤k−2 gap is a correctness issue, not a circular reduction.

full rationale

I walked the derivation chain for the main pair-query characterization (Theorems 1.1 and 1.2), the subset-query theorems, and the low-round algorithms. The upper bound Theorem 1.1 is proven by induction with an explicit recursive algorithm and Claim 3.1; it does not invoke an external result as its own conclusion. The lower bound Theorem 1.2 is built from Turán's Theorem (proved in Section 2.3.1), the repeated Turán Corollary (proved in Section 2.3.2), and the Carving Lemma (proved in Section 2.3.3); the final adversary argument constructs two partitions that agree on all earlier-round answers, which is a standard indistinguishability reduction rather than a restatement of the theorem. The base case r=1 is reproved directly via an unqueried pair yielding indistinguishable 3-partitions, so the citations [MS17a, BLMS24] for the Θ(n^2) non-adaptive bound are not load-bearing. The subset-query lower bounds are obtained by simulating an s-bounded strong query with O(s^2) pair queries and applying the pair lower bound, or by information-theoretic counting; this is an external reduction, not a definitional identity. No parameter is fitted to data and then renamed a prediction; no ansatz is imported solely through a self-citation; no uniqueness theorem is invoked to forbid alternatives. The reader's critique that Theorem 1.2 requires r≤k−2 (Section 2.2 sets ℓ=⌊(k−3)/(r−1)⌋ and requires ℓ≥1) and fails for k=3,r=2 concerns correctness and quantifier accuracy, not circularity: the proof does not assume the theorem it is proving. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities; the paper derives exact bounds though one hidden assumption restricts the main theorem.

assumptions (3)
  • ad hoc to paper The lower bound proof assumes r≤k−2 (so ℓ≥1), though Theorem 1.2 states the bound for all r≥1.
    Section 2.2 defines ℓ := floor((k−3)/(r−1)) and states ℓ≥1 since r≤k−2 by assumption; this restricts the theorem's validity without being stated in the theorem or abstract.
  • standard math Turan's theorem and Jensen's inequality
    Used to find independent sets in the query graph; proved in Section 2.3.
  • domain assumption Known results Θ(nk) adaptive and Θ(n^2) non-adaptive pairwise query complexity
    Used as baselines and for subset query lower bounds; from [MS17a, LM22, BLMS24].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Partitions with Optimal Query and Round Complexities." pith.science (2026). https://pith.science/paper/LTGPXKGN

@misc{pith2026250505009,
  author       = {Pith},
  title        = {Pith review of: Learning Partitions with Optimal Query and Round Complexities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LTGPXKGN}},
  note         = {Machine review of arXiv:2505.05009}
}
abstract

We consider the basic problem of learning an unknown partition of $n$ elements into at most $k$ sets using simple queries that reveal information about a small subset of elements. Our starting point is the well-studied pairwise same-set queries which ask if a pair of elements belong to the same class. It is known that non-adaptive algorithms require $\Theta(n^2)$ queries, while adaptive algorithms require $\Theta(nk)$ queries, and the best known algorithm uses $k-1$ rounds. This problem has been studied extensively over the last two decades in multiple communities due to its fundamental nature and relevance to clustering, active learning, and crowd sourcing. In many applications, it is of high interest to reduce adaptivity while minimizing query complexity. We give a complete characterization of the deterministic query complexity of this problem as a function of the number of rounds, $r$, interpolating between the non-adaptive and adaptive settings: for any constant $r$, the query complexity is $\Theta(n^{1+\frac{1}{2^r-1}}k^{1-\frac{1}{2^r-1}})$. Our algorithm only needs $O(\log \log n)$ rounds to attain the optimal $O(nk)$ query complexity. Next, we consider two generalizations of pairwise queries to subsets $S$ of size at most $s$: (1) weak subset queries which return the number of classes intersected by $S$, and (2) strong subset queries which return the entire partition restricted on $S$. Once again in crowd sourcing applications, queries on large sets may be prohibitive. For non-adaptive algorithms, we show $\Omega(n^2/s^2)$ strong queries are needed. Perhaps surprisingly, we show that there is a non-adaptive algorithm using weak queries that matches this bound up to log-factors for all $s \leq \sqrt{n}$. More generally, we obtain nearly matching upper and lower bounds for algorithms using subset queries in terms of both the number of rounds, $r$, and the query size bound, $s$.

Figures

Figures reproduced from arXiv: 2505.05009 by the authors.

Figure 1
Figure 1. A comparison of weak vs. strong subset queries for non-adaptive and fully adaptive algorithms as a function of the allowed query size, s, ignoring poly log(n) factors. For the purposes of the diagram we have used k ≤ √ n, but note in general there is no such restriction on k. Our results reveal that in the relatively small s regime (s ≤ √ n for non-adaptive and s ≤ √ k for adaptive), strong subset queries give no ad… view at source ↗
Figure 2
Figure 2. An illustration depicting the construction of P1, S(1) and P2, S(2) in the proof of Theorem 1.2. The top-left shows the graph whose edges are the first round queries, Q1 (blue edges). Then, Lemma 2.3 is applied which uses Tur´an’s theorem to find ℓ (in the picture ℓ = 5) independent sets S (1) = S (1) 1 ⊔ · · · ⊔ S (1) 5 ⊂ U with respect to Q1. The partition P1 is defined based on these independent sets (top-right).… view at source ↗
Figure 3
Figure 3. An illustration depicting the final pair of partitions P (1) x,y and P (2) x,y which the r-round algorithm fails to distinguish. The set S is depicted in white. Note that we have not tried to depict the partition within the sets S and U \ S. The point is that the partition P = Pr−1 has been defined a such a way that every queried pair (u, v) ∈ Q1 ∪ · · · ∪ Qr−1 that touches S is such that u, v belong to different se… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: An illustration depicting how Alg. 2 learns the “medium”-sized sets. The sets of the partition are represented by the three colors (here k = 3). The random core set R (chosen in line 14) is large enough so that with high probability it contains a representative from ev…
Figure 5
Figure 5. Figure 5: An illustration depicting the key idea of Alg. 3 (LearnSparse). The green region represents the points belonging to known sets in the partition (the larger sets) and the white regions represent the sets we are trying to learn. The queried set I (pictured in blue) is dr…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 45 canonical work pages

  1. [1]

    Learning a hidden subgraph

    Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discret. Math. , 2005

    work page 2005

  2. [2]

    On learning graphs with edge-detecting queries

    Hasan Abasi and Nader Bshouty. On learning graphs with edge-detecting queries. In Proceedings of the 30th International Conference on Algorithmic Learning Theory , 2019

    work page 2019

  3. [3]

    Community detection and stochastic block models: recent developments

    Emmanuel Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research , 18(177):1--86, 2018

    work page 2018

  4. [4]

    Learning a hidden matching

    Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM J. Comput. , 2004

    work page 2004

  5. [5]

    Aggregating inconsistent information: R anking and clustering

    Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: R anking and clustering. Journal of the ACM , 55(5):1--27, 2008

    work page 2008

  6. [6]

    Cut query algorithms with star contraction

    Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, and Danupon Nanongkai. Cut query algorithms with star contraction. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS) , 2022

    work page 2022

  7. [7]

    Combinatorial search

    Martin Aigner. Combinatorial search. John Wiley & Sons, Inc. , 1988

    work page 1988

  8. [8]

    Clustering with same-cluster queries

    Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David. Clustering with same-cluster queries. Advances in neural information processing systems , 2016

    work page 2016

Show all 51 references
  1. [9]

    On the query complexity of connectivity with global queries

    Arinta Auza and Troy Lee. On the query complexity of connectivity with global queries. arXiv preprint arXiv:2109.02115 , 2021

    2021 arXiv

  2. [10]

    Correlation clustering

    Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning , 56(1):89--113, 2004

    2004

  3. [11]

    Exact recovery of mangled clusters with same-cluster queries

    Marco Bressan, Nicol \`o Cesa-Bianchi, Silvio Lattanzi, and Andrea Paudice. Exact recovery of mangled clusters with same-cluster queries. Advances in Neural Information Processing Systems , 2020

    2020

  4. [12]

    Clustering with non-adaptive subset queries

    Hadley Black, Euiwoong Lee, Arya Mazumdar, and Barna Saha. Clustering with non-adaptive subset queries. In Advances in Neural Information Processing Systems. (NeurIPS) , 2024

    2024

  5. [13]

    Bshouty and Hanna Mazzawi

    Nader H. Bshouty and Hanna Mazzawi. Algorithms for the coin weighing problems with the presence of noise. Electron. Colloquium Comput. Complex. , TR11-124 , 2011

    2011

  6. [14]

    Bshouty and Hanna Mazzawi

    Nader H. Bshouty and Hanna Mazzawi. On parity check (0, 1)-matrix over z\( ^ p \). In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2011

    2011

  7. [15]

    Understanding the cluster lp for correlation clustering

    Nairen Cao, Vincent Cohen-Addad , Euiwoong Lee, Shi Li, Alantha Newman, and Lukas Vogl. Understanding the cluster lp for correlation clustering. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC) , 2024

    2024

  8. [16]

    Polynomial time optimal query algorithms for finding graphs with arbitrary real weights

    Sung-Soon Choi. Polynomial time optimal query algorithms for finding graphs with arbitrary real weights. In Conference on Learning Theory , pages 797--818. PMLR, 2013

    2013

  9. [17]

    Optimal query complexity bounds for finding graphs

    Sung-Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. In Proceedings of the fortieth annual ACM symposium on Theory of computing , 2008

    2008

  10. [18]

    A query algorithm for learning a spanning forest in weighted undirected graphs

    Deeparnab Chakrabarty and Hang Liao. A query algorithm for learning a spanning forest in weighted undirected graphs. In Proceedings, International Conference on Algorithmic Learning Theory (ALT) , 2023

    2023

  11. [19]

    Learning partitions using rank queries

    Deeparnab Chakrabarty and Hang Liao. Learning partitions using rank queries. In Proceedings, Foundations of Software Technology and Theoretical Computer Science. (FSTTCS) , 2024

    2024

  12. [20]

    Determination of a subset from certain combinatorial properties

    David G Cantor and WH Mills. Determination of a subset from certain combinatorial properties. Canadian Journal of Mathematics , 18:42--48, 1966

    1966

  13. [21]

    Near optimal LP rounding algorithm for correlation clustering on complete and complete k -partite graphs

    Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. Near optimal LP rounding algorithm for correlation clustering on complete and complete k -partite graphs. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages 219--...

    2015

  14. [22]

    Combinatorial group testing and its applications

    Dingzhu Du and Frank K Hwang. Combinatorial group testing and its applications. World Scientific , 12, 2000

    2000

  15. [23]

    Combinatorial group testing and its applications , volume 12

    Dingzhu Du, Frank K Hwang, and Frank Hwang. Combinatorial group testing and its applications , volume 12. World Scientific, 2000

    2000

  16. [24]

    Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy

    Susan B. Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy. Top-k and clustering with noisy comparisons. ACM Trans. Database Syst. , 2014

    2014

  17. [25]

    Optimal algorithms for learning partitions with faulty oracles

    Adela DePavia, Olga Medrano Martin del Campo, and Erasmo Tani. Optimal algorithms for learning partitions with faulty oracles. In Advances in Neural Information Processing Systems. (NeurIPS) , 2024

    2024

  18. [26]

    Clustering with queries under semi-random noise

    Alberto Del Pia, Mingchen Ma, and Christos Tzamos. Clustering with queries under semi-random noise. In Conference on Learning Theory . PMLR, 2022

    2022

  19. [27]

    Crowddb: Query processing with the vldb crowd

    Amber Feng, Michael Franklin, Donald Kossmann, Tim Kraska, Samuel R Madden, Sukriti Ramesh, Andrew Wang, and Reynold Xin. Crowddb: Query processing with the vldb crowd. 2011

    2011

  20. [28]

    Franklin, Donald Kossmann, Tim Kraska, Sukriti Ramesh, and Reynold Xin

    Michael J. Franklin, Donald Kossmann, Tim Kraska, Sukriti Ramesh, and Reynold Xin. Crowddb: answering queries with crowdsourcing. In Proceedings of the 2011 international conference on Management of data , pages 61--72, New York, NY, USA, 2011. ACM

    2011

  21. [29]

    Probabilistic group testing with a linear number of tests

    Larkin Flodin and Arya Mazumdar. Probabilistic group testing with a linear number of tests. In 2021 IEEE International Symposium on Information Theory (ISIT) , pages 1248--1253. IEEE, 2021

    2021

  22. [30]

    Towards active learning on graphs: An error bound minimization approach

    Quanquan Gu and Jiawei Han. Towards active learning on graphs: An error bound minimization approach. In 2012 IEEE 12th International Conference on Data Mining , pages 882--887. IEEE, 2012

    2012

  23. [31]

    Optimal reconstruction of graphs under the additive model

    Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica , 28(1):104--124, 2000

    2000

  24. [32]

    Same-cluster querying for overlapping clusters

    Wasim Huleihel, Arya Mazumdar, Muriel M \'e dard, and Soumyabrata Pal. Same-cluster querying for overlapping clusters. Advances in Neural Information Processing Systems , 32, 2019

    2019

  25. [33]

    Hwang and V

    F. Hwang and V. S\' o s. Non-adaptive hypergeometric group testing. Studia Sci. Math. Hungar , 1987

    1987

  26. [34]

    Active learning with simple questions

    Vasilis Kontonis, Mingchen Ma, and Christos Tzamos. Active learning with simple questions. In Conference on Learning Theory (COLT) , 2024

    2024

  27. [35]

    Learning spanning forests optimally in weighted undirected graphs with CUT queries

    Hang Liao and Deeparnab Chakrabarty. Learning spanning forests optimally in weighted undirected graphs with CUT queries. In Proceedings, International Conference on Algorithmic Learning Theory (ALT) , 2024

    2024

  28. [36]

    Predicting positive and negative links in online social networks

    Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th international conference on World wide web , 2010

    2010

  29. [37]

    On a combinatorial problem in number theory

    Bernt Lindstr\" o m. On a combinatorial problem in number theory. Canadian Mathematical Bulletin , 1965

    1965

  30. [38]

    Tight query complexity bounds for learning graph partitions

    Xizhi Liu and Sayan Mukherjee. Tight query complexity bounds for learning graph partitions. In Conference on Learning Theory (COLT) , 2022

    2022

  31. [39]

    Nonadaptive group testing with random set of defectives

    Arya Mazumdar. Nonadaptive group testing with random set of defectives. IEEE Transactions on Information Theory , 2016

    2016

  32. [40]

    Semisupervised clustering, and-queries and locally encodable source coding

    Arya Mazumdar and Soumyabrata Pal. Semisupervised clustering, and-queries and locally encodable source coding. Advances in Neural Information Processing Systems , 30, 2017

    2017

  33. [41]

    Recovering unbalanced communities in the stochastic block model with application to clustering with a faulty oracle

    Chandra Sekhar Mukherjee, Pan Peng, and Jiapeng Zhang. Recovering unbalanced communities in the stochastic block model with application to clustering with a faulty oracle. Advances in Neural Information Processing Systems , 36, 2024

    2024

  34. [42]

    Clustering with noisy queries

    Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Advances in Neural Information Processing Systems. (NeurIPS) , 2017

    2017

  35. [43]

    Query complexity of clustering with side information

    Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In Advances in Neural Information Processing Systems. (NeurIPS) , 2017

    2017

  36. [44]

    A theoretical analysis of first heuristics of crowdsourced entity resolution

    Arya Mazumdar and Barna Saha. A theoretical analysis of first heuristics of crowdsourced entity resolution. In Proceedings of the AAAI Conference on Artificial Intelligence , 2017

    2017

  37. [45]

    Active learning for crowd-sourced databases

    Barzan Mozafari, Purnamrita Sarkar, Michael J Franklin, Michael I Jordan, and Samuel Madden. Active learning for crowd-sourced databases. arXiv preprint arXiv:1209.3686 , 2012

    2012 arXiv

  38. [46]

    Predicting signed edges with o(n^ 1+o(1) n) queries

    Michael Mitzenmacher and Charalampos E Tsourakakis. Predicting signed edges with o(n^ 1+o(1) n) queries. arXiv preprint arXiv:1609.00750 , 2016

    2016 arXiv

  39. [47]

    Explicit non-adaptive combinatorial group testing schemes

    Ely Porat and Amir Rothschild. Explicit non-adaptive combinatorial group testing schemes. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008 , Lecture Notes in Computer Science, 2008

    2008

  40. [48]

    Learning and verifying graphs using queries with a focus on edge counting

    Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In Algorithmic Learning Theory (ALT) , 2007

    2007

  41. [49]

    Computing exact minimum cuts without knowing the graph

    Aviad Rubinstein, Tselil Schramm, and S Matthew Weinberg. Computing exact minimum cuts without knowing the graph. In Innovations in Theoretical Computer Science (ITCS) , 2018

    2018

  42. [50]

    Correlation clustering with same-cluster queries bounded by optimal cost

    Barna Saha and Sanjay Subramanian. Correlation clustering with same-cluster queries bounded by optimal cost. In 27th Annual European Symposium on Algorithms (ESA 2019) . Schloss-Dagstuhl-Leibniz Zentrum f \"u r Informatik, 2019

    2019

  43. [51]

    Franklin, and Jianhua Feng

    Jiannan Wang, Tim Kraska, Michael J. Franklin, and Jianhua Feng. Crowder: crowdsourcing entity resolution. Proc. VLDB Endow. , 5(11):1483–1494, July 2012

    2012

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.