Pith. sign in

REVIEW 2 major objections 4 minor 1 cited by

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Counting connected components in vertex subsets is enough to rebuild any graph, and the number of queries needed is now known exactly.

desk verdict New CC-query model with tight bounds, but the main adaptive proof has a false edge test; the fix is trivial and the rest holds. read the letter →

arxiv 2506.08405 v1 pith:AE3MTDL7 submitted 2025-06-10 cs.DS cs.ITcs.LGmath.IT

Hadley Black , Arya Mazumdar , Barna Saha , Yinzhan Xu This is my paper
classification cs.DScs.ITcs.LGmath.IT MSC 68Q2568R10
keywords graphreconstructionconnectedcomponentsquerycomplexityadaptivealgorithmsnon-adaptivelowerboundsgrouptestinginducedsubgraphqueriesforestsampling
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

The paper asks how many times an oracle must be asked how many connected components a vertex subset induces in order to fully reconstruct a hidden graph. It settles the question with matching upper and lower bounds: every n-node m-edge graph can be recovered adaptively with O(m log n / log m) queries in expectation, and no adaptive randomized algorithm can do better. The same query model is far weaker without adaptivity: any non-adaptive algorithm needs Ω(n²) queries even when the graph has only O(n) edges. A two-round algorithm with O(m log n + n log² n) queries interpolates between these extremes. The result pinpoints the exact power of one of the most basic graph statistics as a query primitive.

What carries the argument

The load-bearing identity is that on any forest, the number of edges in an induced subgraph equals |U| − CC(U), so one CC-query can simulate one edge-density query. The adaptive algorithm samples vertex subsets at probability p = Θ((mD)^−1/3) so that the induced subgraph is a matching (hence a forest) with constant probability, discovers edges there using a forest-reconstruction subroutine, and repeats with the discovered edges removed. The binary-search edge test — adding a vertex to a set leaves the component count unchanged exactly when the vertex has a neighbor in that set — is used to recover leftover edges when few remain. The two-round algorithm first estimates every vertex's degree by sampling random subsets and checking whether the component count changes, then recovers each neighborhood by group testing, where each OR-query is simulated by two CC-queries. Forest reconstruction itself relies on a prior density-query reconstruction algorithm, simulated one-for-one on induced subgraphs.

What would settle it

On the four-vertex graph with vertices a, b, c, v and edges a-c, c-b, v-a, v-b, query U = {a, b} and U ∪ {v}: the oracle returns CC(U) = 2 and CC(U ∪ {v}) = 1, so the Lemma 2.3 equivalence 'there is an edge between v and U iff CC(U) = CC(U ∪ {v})' is false. Running the binary-search subroutine from Lemma 2.3 on this graph would therefore either miss the edges (v, a) and (v, b) or exceed the claimed query bound, exposing the load-bearing premise.

Watch

Extended reading notes

Core claim

The central claim is that the number of connected components in induced subgraphs gives a graph reconstruction model with query complexity Θ(m log n / log m) for adaptive algorithms, for every value of m. The upper bound is proved by an algorithm that alternates between reconstructing edges inside similar-degree vertex sets — by randomly sampling induced subgraphs that become matchings, so that one CC-query simulates one edge-count query on a forest — and reconstructing edges between very different-degree sets by coloring and applying a forest-reconstruction subroutine. The matching lower bound is proved by an information-theoretic counting argument for sparse graphs and, for dense graphs, by reducing from unstructured search on the missing edge of an almost-complete graph. A separate lower bound shows that non-adaptive algorithms require Ω(n²) queries even for graphs with O(n) edges, and a two-round algorithm achieves O(m log n + n log² n) queries in the worst case.

Load-bearing premise

The adaptive algorithm's binary-search edge test assumes that adding a vertex to a set of vertices changes the component count exactly when the vertex has no neighbor in that set, but this equivalence fails when the vertex has neighbors in two different components of the set, because then the count drops instead of staying level.

Editorial extensions

If this is right

  • Adaptive CC-queries are optimal for every m, matching the weighted-additive query bound and beating IS-queries whenever ω(1) < m < n^{2−ε}.
  • Non-adaptive algorithms are essentially forced to query quadratically many sets even on sparse graphs, so adaptivity yields a separation from near-linear to quadratic query cost.
  • A two-round algorithm with O(m log n + n log² n) queries shows that most of the benefit of adaptivity can be captured in a single extra round, though the exact two-round optimum is left open.
  • The non-adaptive lower-bound construction, based on graphs built from length-2 paths, shows that any one-round algorithm must in effect ask about every pair of vertices.
  • The forest-simulation technique gives a general template for transferring density-query algorithms into the CC-query model.

Reading between the lines

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

  • If the binary-search edge test could be made robust to vertices that touch multiple components of the queried set, the same Θ(m log n / log m) upper bound would extend to noisy or approximate CC-query models.
  • The degree-estimation routine — sampling random subsets and checking whether the component count changes — could plausibly be adapted to estimate other monotone graph statistics, such as the total number of edges, using only CC-queries.
  • The lower-bound graphs, which are unions of 2-paths plus one optional chord, may transfer to other query models where a single query can distinguish only pairs that are both contained in the queried set.
  • The exact agreement with the weighted-additive query bound raises the question of whether CC-queries can simulate weighted edge-count queries in general, or whether the similarity is coincidental to the forest case.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper introduces a graph reconstruction model in which a query returns the number of connected components of an induced subgraph. The main claims are: an adaptive algorithm with optimal expected query complexity Θ(m log n / log m) for n-node m-edge graphs; an Ω(n^2) lower bound for non-adaptive algorithms even when the graph has only O(n) edges; and a two-round algorithm using O(m log n + n log^2 n) queries. The adaptive upper bound is built from a forest-reconstruction subroutine that simulates additive queries through CC queries, a randomized matching-sampling routine, and a degree-threshold decomposition of the vertex set. The lower bounds use information-theoretic counting and a reduction from unstructured search.

Significance. If the results hold, they settle the adaptive query complexity of CC-query reconstruction and establish a strong separation between adaptive and non-adaptive algorithms, as well as a contrast with additive and cross-additive query models. The non-adaptive lower bound is clean and robust, and the two-round algorithm is an elegant application of group testing. However, the main adaptive upper bound currently rests on an incorrect edge-detection equivalence in Lemma 2.3, and the proof's final verification step assumes exact knowledge of the edge count even though the theorem statement allows only an upper bound. Both issues are identifiable, local, and appear repairable without changing the claimed rates.

major comments (2)
  1. [Section 2.1, Lemma 2.3] The edge-detection equivalence stated in the proof is false: the text claims that for any U ⊆ V \ {v}, there is at least one edge between v and U if and only if CC(U) = CC(U ∪ {v}). If v has neighbors in k ≥ 2 distinct connected components of G[U], then CC(U ∪ {v}) = CC(U) − k + 1, so the counts are unequal even though an edge exists. For example, with U = {a,b} independent and v adjacent to both, CC(U) = 2 and CC(U ∪ {v}) = 1. Since the binary-search subroutine halts when this test reports no edge, it can silently miss all edges from v to such a U. Lemma 2.3 is subsequently used in Corollary 3.8 and hence in the main adaptive algorithm of Theorem 1.1, so the upper bound is unproven as written. The fix is to test the correct condition CC(U ∪ {v}) < CC(U) + 1 (equivalently CC(U ∪ {v}) ≤ CC(U)), which costs two CC-queries per comparison and preserves the asymptotic O((n + m_u) log(n^2/(n + m_u))) bound.
  2. [Section 3.3, proof of Theorem 1.1] The final verification and boosting step accepts a proposed reconstruction only when the number of discovered edges equals the input m. This treats m as the exact edge count, but Theorem 1.1 is stated for an upper bound m on the number of edges. For a graph with m' < m actual edges, a run that has correctly found every edge will have |K| = m' ≠ m, so the test never passes and the algorithm loops forever; consequently the expected query complexity is not finite. The theorem should either be restated with exact m as input, or the algorithm must be given a stopping rule that certifies completeness without knowing the exact edge count, for example by running a corrected Lemma 2.3 to completion and verifying only that no false edges are output.
minor comments (4)
  1. [Section 3.3, last line of Theorem 1.1 proof] The displayed final bound 'O(m log m / log n)' should read 'O(m log n / log m)'.
  2. [Section 2.1, before Lemma 2.3] The phrase 'reconstructs the whoel graph' contains a typo; it should be 'whole graph'.
  3. [Section 5.2, first paragraph] The claim that a CC-query 'returns at most log(m + 1) bits of information' deserves a one-line justification: for any fixed query set U, the answer CC(U) lies in an interval of length at most m + 1 because CC(U) is between |U| − m and |U|.
  4. [Section 4, Lemmas 4.4 and 4.5] The vector notation switches between x_u in Lemma 4.4 and v in Lemma 4.5; please align the notation so that the support of the vector is unambiguously the neighbor set of the queried vertex.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the adaptive bounds are built from an external black-box reconstruction theorem and independent information-theoretic lower bounds; the self-cited group-testing lemma is standard and not equivalent to the target result.

full rationale

The paper's main derivation chain is self-contained against external inputs rather than circular. Theorem 1.1 uses Theorem 2.1 (Mazzawi 2010) as an external black box and Lemma 2.2 simulates each density query by one CC-query using the exact identity density(U)=|U|-CC(U) on forests; no fitted parameter is then renamed as a prediction. The lower bounds in Theorems 1.2 and 1.3 are independent combinatorial and information-theoretic arguments that do not rely on the upper-bound algorithms. The only author-self-citation that is technically load-bearing is Lemma 4.5, attributed to the authors' prior work [BLMS24], but that lemma is a standard non-adaptive group-testing primitive for OR queries, it is parameter-free, and it is used only in the secondary two-round algorithm; it is not equivalent to, and does not presuppose, the CC-reconstruction theorem being proved. The skeptical remarks in the reader's take identify genuine correctness concerns (the claimed equivalence 'there is at least one edge between v and U iff CC(U)=CC(U∪{v})' fails when v has neighbors in multiple components of G[U], and the final verification step assumes the input m is exact rather than an upper bound), but these are non-circular correctness bugs, not cases where a result reduces to its own input. No claim in the paper is derived by defining a quantity in terms of the target, no fitted value is presented as an independent prediction, and no uniqueness theorem is imported from the authors' prior work to force a choice. Accordingly the circularity score is 0.

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

No free parameters are fitted to data; the constants p, T_i, and α_i are defined analytically from n and m. The paper introduces no new physical or mathematical entities; the CC-query oracle is the query model under study, not an invented entity.

assumptions (4)
  • domain assumption Theorem 2.1 from Mazzawi 2010: additive/density queries reconstruct an n-node m-edge graph using O(m log n / log m) queries.
    Used as a black box in Lemma 2.2 for forest reconstruction; the paper does not reprove it.
  • domain assumption Lemma 4.5 from BLMS24: non-adaptive OR-query group testing recovers a d-sparse support with O(d log(n/α)) queries.
    Used in the two-round algorithm; it is a self-cited prior result, but the central adaptive result does not depend on it.
  • standard math Standard concentration and convexity tools (Chernoff, Hoeffding, Markov, Jensen).
    Used throughout the probabilistic analyses in Sections 2, 3, and 4.
  • domain assumption The CC-oracle answers exactly, with no errors or adversarial noise.
    The model assumes exact component counts for any queried induced subgraph.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs." pith.science (2026). https://pith.science/paper/AE3MTDL7

@misc{pith2026250608405,
  author       = {Pith},
  title        = {Pith review of: Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AE3MTDL7}},
  note         = {Machine review of arXiv:2506.08405}
}
abstract

The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $\Theta(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $\Omega(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Experimental Assortments for Choice Estimation and Nest Identification

    stat.ME 2026-02 conditional novelty 7.0 of 10

    A binary-code experiment design with O(log n) assortments, plus a boost-factor algorithm, provably recovers substitution nests in Nested Logit models and improves choice prediction.

Reference graph

Works this paper leans on

53 extracted references · 50 canonical work pages · cited by 1 Pith paper

  1. [1]

    Learning a hidden subgraph

    Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discret. Math. , 18(4):697--712, 2005

    work page 2005

  2. [2]

    Hasan Abasi and Nader H. Bshouty. On learning graphs with edge-detecting queries. In Algorithmic Learning Theory, ALT 2019 , volume 98 of Proceedings of Machine Learning Research , pages 3--30. PMLR , 2019

    work page 2019

  3. [3]

    Learning a hidden matching

    Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM J. Comput. , 33(2):487--501, 2004

    work page 2004

  4. [4]

    Learning a hidden graph using O(log n) queries per edge

    Dana Angluin and Jiang Chen. Learning a hidden graph using O(log n) queries per edge. J. Comput. Syst. Sci. , 74(4):546--556, 2008

    work page 2008

  5. [5]

    Graph connectivity and single element recovery via linear and OR queries

    Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph connectivity and single element recovery via linear and OR queries. In European Symposium on Algorithms, (ESA) , 2021

    work page 2021

  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 of the 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022) , pages 507--518, 2022

    work page 2022

  7. [7]

    Clustering with same-cluster queries

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

    work page 2016

  8. [8]

    On the query complexity of connectivity with global queries

    Arinta Auza and Troy Lee. On the query complexity of connectivity with global queries. CoRR , abs/2109.02115, 2021

    arXiv 2021

Show all 53 references
  1. [9]

    Deterministic edge connectivity and max flow using subquadratic cut queries

    Aditya Anand, Thatchaphol Saranurak, and Yunfan Wang. Deterministic edge connectivity and max flow using subquadratic cut queries. In Symposium on Discrete Algorithms, SODA , 2025

    2025

  2. [10]

    Clustering with interactive feedback

    Maria-Florina Balcan and Avrim Blum. Clustering with interactive feedback. In International Conference on Algorithmic Learning Theory , pages 316--328. Springer, 2008

    2008

  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 , 33:9324--9334, 2020

    2020

  4. [12]

    Near-optimal column-based matrix reconstruction

    Christos Boutsidis, Petros Drineas, and Malik Magdon - Ismail. Near-optimal column-based matrix reconstruction. SIAM J. Comput. , 43(2):687--717, 2014

    2014

  5. [13]

    Shankar Ram

    Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Mat \' u s Mihal \' a k, and L. Shankar Ram. Network discovery and verification. IEEE J. Sel. Areas Commun. , 24(12):2168--2181, 2006

    2006

  6. [14]

    Estimating the number of species: a review

    John Bunge and Michael Fitzpatrick. Estimating the number of species: a review. Journal of the American statistical Association , 88(421):364--373, 1993

    1993

  7. [15]

    Optimal distance query reconstruction for graphs without long induced cycles

    Paul Bastide and Carla Groenland. Optimal distance query reconstruction for graphs without long induced cycles. CoRR , abs/2306.05979, 2023

    2023 arXiv

  8. [16]

    Clustering with non-adaptive subset queries

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

    2024

  9. [17]

    Bshouty and Hanna Mazzawi

    Nader H. Bshouty and Hanna Mazzawi. Reconstructing weighted graphs with minimal query complexity. Theor. Comput. Sci. , 412(19):1782--1790, 2011

    2011

  10. [18]

    Bshouty and Hanna Mazzawi

    Nader H. Bshouty and Hanna Mazzawi. Toward a deterministic polynomial time algorithm with optimal additive query complexity. Theor. Comput. Sci. , 2012

    2012

  11. [19]

    Bshouty and Hanna Mazzawi

    Nader H. Bshouty and Hanna Mazzawi. On parity check (0, 1)-matrix over \( z \) \( _ p \). SIAM J. Discret. Math. , 29(1):631--657, 2015

    2015

  12. [20]

    Nearly optimal communication and query complexity of bipartite matching

    Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. Nearly optimal communication and query complexity of bipartite matching. In Foundations of Computer Science, FOCS , 2022

    2022

  13. [21]

    Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu

    Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing ( STOC 2015) , pages 163--172, 2015

    2015

  14. [22]

    Separating words and trace reconstruction

    Zachary Chase. Separating words and trace reconstruction. In Symposium on Theory of Computing (STOC) , 2021

    2021

  15. [23]

    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 Proceedings of the 26th Annual Conference on Learning Theory ( COLT 2013) , pages 797--818, 2013

    2013

  16. [24]

    Optimal query complexity bounds for finding graphs

    Sung - Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. Artif. Intell. , 174(9-10):551--569, 2010

    2010

  17. [25]

    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 International Conference on Algorithmic Learning Theory (ALT) , 2023

    2023

  18. [26]

    Learning partitions using rank queries

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

    2024

  19. [27]

    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 Adv. in Neu. Inf. Proc. Sys. (NeurIPS) , 2024

    2024

  20. [28]

    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 , pages 5278--5313. PMLR, 2022

    2022

  21. [29]

    Network discovery and verification with distance queries

    Thomas Erlebach, Alexander Hall, Michael Hoffmann, and Mat \' u s Mihal \' a k. Network discovery and verification with distance queries. In Proceedings of the 6th Italian Conference on Algorithms and Complexity ( CIAC 2006) , pages 69--80, 2006

    2006

  22. [30]

    Estimation of the number of connected components in a graph by using a sampled subgraph

    Ove Frank. Estimation of the number of connected components in a graph by using a sampled subgraph. Scandinavian Journal of Statistics , pages 177--188, 1978

    1978

  23. [31]

    Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping

    Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discret. Appl. Math. , 88(1-3):147--165, 1998

    1998

  24. [32]

    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

  25. [33]

    MST in log-star rounds of congested clique

    Mohsen Ghaffari and Merav Parter. MST in log-star rounds of congested clique. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC) , pages 19--28. ACM , 2016

    2016

  26. [34]

    On the power of additive combinatorial search model

    Vladimir Grebinski. On the power of additive combinatorial search model. In Proceedings of the 4th Annual International Conference on Computing and Combinatorics ( COCOON ) , pages 194--203, 1998

    1998

  27. [35]

    Matchings, matroids and submodular functions

    Nicholas James Alexander Harvey. Matchings, matroids and submodular functions . PhD thesis, Massachusetts Institute of Technology, 2008

    2008

  28. [36]

    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

  29. [37]

    Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

    Nina Holden, Robin Pemantle, and Yuval Peres. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Conference On Learning Theory, COLT , 2018

    2018

  30. [38]

    Reconstructing cactus graphs from shortest path information - (extended abstract)

    Evangelos Kranakis, Danny Krizanc, and Yun Lu. Reconstructing cactus graphs from shortest path information - (extended abstract). In Proceedings of the 11th International Conference on Algorithmic Aspects in Information and Management ( AAIM 2016) , pages 150--161, 2016

    2016

  31. [39]

    Implicit routing and shortest path information (extended abstract)

    Evangelos Kranakis, Danny Krizanc, and Jorge Urrutia. Implicit routing and shortest path information (extended abstract). In Proceedings of the 2nd Colloquium on Structural Information and Communication Complexity ( SIROCCO 1995) , pages 101--112, 1995

    1995

  32. [40]

    Near-linear query complexity for graph inference

    Sampath Kannan, Claire Mathieu, and Hang Zhou. Near-linear query complexity for graph inference. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming ( ICALP 2015) , pages 773--784, 2015

    2015

  33. [41]

    Graph reconstruction and verification

    Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms , 2018

    2018

  34. [42]

    Graph reconstruction via MIS queries

    Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph reconstruction via MIS queries. In Innovations in Theoretical Computer Science (ITCS) , 2025

    2025

  35. [43]

    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 International Conference on Algorithmic Learning Theory (ALT) , 2024

    2024

  36. [44]

    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 , pages 167--181. PMLR, 2022

    2022

  37. [45]

    Optimally reconstructing weighted graphs using queries

    Hanna Mazzawi. Optimally reconstructing weighted graphs using queries. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA 2010) , pages 608--615, 2010

    2010

  38. [46]

    Clustering with noisy queries

    Arya Mazumdar and Barna Saha. Clustering with noisy queries. In Adv. in Neu. Inf. Proc. Sys. (NeurIPS) , 2017

    2017

  39. [47]

    Query complexity of clustering with side information

    Arya Mazumdar and Barna Saha. Query complexity of clustering with side information. In Adv. in Neu. Inf. Proc. Sys. (NeurIPS) , 2017

    2017

  40. [48]

    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

  41. [49]

    Tsourakakis

    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

  42. [50]

    Graph reconstruction via distance oracles

    Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming ( ICALP 2013) , pages 733--744, 2013

    2013

  43. [51]

    A simple algorithm for graph reconstruction

    Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. Random Struct. Algorithms , 2023

    2023

  44. [52]

    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 Proceedings of the 18th International Conference on Algorithmic Learning Theory ( ALT 2007) , pages 285--297, 2007

    2007

  45. [53]

    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

Pith tools

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