Pith. sign in

REVIEW 3 major objections 5 minor 34 references

Complexity of learning matchings and half graphs via edge queries

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

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

Pith's one-line read Learning a hidden matching with edge queries requires n(n-1)/2 queries deterministically and Theta(n^2) even with randomization.

desk verdict Solid paper with a genuine new randomized lower bound for matchings; the deterministic proof has a repairable gap that doesn't touch the main results. read the letter →

arxiv 2507.03151 v1 pith:A4CJQJOY submitted 2025-07-03 cs.CC cs.DMmath.CO

Nikhil S. Mande , Swagato Sanyal , Viktor Zamaraev This is my paper · ORCID
classification cs.CCcs.DMmath.CO MSC 68Q1705C85
keywords edgequeriesgraphreconstructionquerycomplexitymatchingshalfgraphsrandomizedlowerboundsquantumnuts-and-boltssorting
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 studies the number of yes/no edge queries needed to identify a hidden bipartite graph from a known family, where a query asks whether a given left vertex is adjacent to a given right vertex. For matchings, whose adjacency matrices are permutation matrices, it proves the deterministic cost is exactly n(n-1)/2 and the randomized cost is Theta($n^{2}$), so randomness does not reduce the asymptotic cost. For half graphs, whose adjacency matrices are row and column permutations of the lower triangular matrix, it proves tight Theta(n log n) bounds in deterministic and randomized settings in the column-permuted case and randomized and quantum settings in the general case, by showing the problems are exactly equivalent to natural sorting problems. These results matter because edge queries are the most basic possible access to a graph, and the paper shows where this weak model is powerful and where it is not.

What carries the argument

The main objects are the matrix families: $M_n$, the $n \times n$ permutation matrices representing matchings; $C_n$, the column permutations of the lower triangular matrix $L_n$; and $H_n$, the row and column permutations of $L_n$. The randomized matching lower bound is carried by a classical adversary relation over pairs of matchings that differ by one column swap, where each query can separate only one pair in the relation, forcing $\Omega(n^2)$ queries. The half-graph results are carried by exact bijections: an edge query to a matrix in $C_n$ corresponds to a threshold comparison in sorting a permutation of $[n]$, and an edge query to a matrix in $H_n$ corresponds to a cross-list comparison in perfectly interleaved bipartite sorting. The upper bounds use binary search per column and a quicksort-style recursion whose row comparisons are implemented by a search subroutine (classical or quantum) on the XOR of two rows.

What would settle it

Run an optimal deterministic algorithm for matchings on the all-zero oracle and record the queried pairs; if at its leaf some above-diagonal entry (i,j) is unqueried while its mirror (j,i) is also unqueried yet the identity matching is the only consistent output, then Lemma 3.2's key assumption is violated and the proof would need repair.

Watch

Extended reading notes

Core claim

The paper's central claim is that the edge-query complexity of learning a hidden matching is exactly n(n-1)/2 deterministically and Theta($n^{2}$) for bounded-error randomized algorithms, with the new contribution being the randomized lower bound. It also claims that learning a column-permuted half graph is equivalent to sorting an unknown permutation with threshold comparisons, yielding tight Theta(n log n) deterministic and randomized bounds, and that learning a general half graph is equivalent to perfectly interleaved bipartite sorting, a generalization of nuts-and-bolts sorting, yielding a tight Theta(n log n) randomized bound and a tight Theta(n log n) quantum bound. Along the way it gives a simple quicksort-style randomized algorithm with O(n $log^{2}$ n) edge queries and a quantum variant that reaches O(n log n).

Load-bearing premise

The deterministic matching lower bound assumes that along the all-zero path, any query below the diagonal also comes with a query to the mirrored entry above the diagonal at no extra cost; an arbitrary deterministic algorithm is not obliged to do this, and without that assumption the proof cannot force an untouched 2x2 block.

Editorial extensions

If this is right

  • For matchings, the quadratic randomized lower bound rules out any subquadratic randomized edge-query algorithm, so the naive strategy is asymptotically optimal.
  • For column-permuted half graphs, the equivalence with threshold sorting means any improvement in either problem transfers immediately to the other.
  • For general half graphs, the quicksort-style algorithm provides a simple $O(n \log^2 n)$ randomized solution, and its quantum variant reaches the tight $O(n \log n)$ bound.
  • Quantum algorithms help for matchings, where the complexity drops from $\Theta(n^2)$ to $\Theta(n^{1.5})$, but not for half graphs, where both randomized and quantum complexities are $\Theta(n \log n)$.

Reading between the lines

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

  • The equivalence between half-graph learning and perfectly interleaved bipartite sorting suggests that closing the deterministic gap for $H_n$ ($\Omega(n \log n)$ versus $O(n^2)$) depends on the unresolved deterministic complexity of nuts-and-bolts-style sorting.
  • The paper's Appendix B certificate, which pins down a half graph with only $O(n)$ zero entries, indicates the matching lower-bound technique of following the all-zero path and exposing an untouched $2 \times 2$ block cannot be transplanted to half graphs; one could check other graph families for similarly small certificates.
  • A natural next probe is to replace the one-column-swap relation in the randomized adversary proof with $k$-swap relations to see whether the $\Theta(n^2)$ matching bound is stable under stronger relations, or whether average-case matching learning can bypass it.
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

3 major / 5 minor

Summary. The paper studies the edge-query complexity of reconstructing a hidden bipartite graph from three families: permutation matrices (matchings), column permutations of the lower-triangular matrix (column-permuted half graphs), and row/column permutations of the lower-triangular matrix (general half graphs). For matchings it proves D(Mn)=n(n−1)/2, R(Mn)=Θ(n²), and cites Q(Mn)=Θ(n^{1.5}); for column-permuted half graphs it proves Θ(n log n) deterministic and randomized bounds and an Ω(n)–O(n log n) quantum bound; for general half graphs it gives a quicksort-style O(n log² n) randomized algorithm and an O(n log n) quantum algorithm, with a tight Ω(n log n) quantum lower bound via prior sorting lower bounds. The paper also establishes equivalences between these learning problems and threshold sorting and perfectly interleaved bipartite sorting.

Significance. If correct, the main contribution is the new Ω(n²) randomized lower bound for learning matchings via edge queries, which matches the deterministic upper bound and is obtained by a clean application of Aaronson's adversary method. The equivalence lemmas connecting half-graph learning to sorting problems are useful observations that transfer known sorting results to the query model, and the quicksort-style algorithms are simple and instructive. Parts of the paper are carefully executed, notably the adversary calculation for R(Mn), the upper bounds, and the certificate construction in Appendix B. However, three proof gaps need to be repaired: the deterministic matching lower bound contains an unjustified symmetry assumption, the threshold-sorting equivalence has an off-by-one error, and the quantum adversary lower bound for column-permuted half graphs omits the required sets X and Y.

major comments (3)
  1. [Section 3.1, Lemma 3.2] The proof assumes that a query to (i,j) with i>j is accompanied by a query to (j,i) 'at no extra cost,' and also that no diagonal entries are queried on the all-0 path because all query outcomes are 0. Neither statement is valid for an arbitrary deterministic decision tree: a below-diagonal query need not have its symmetric counterpart queried, and a diagonal query would also be answered 0 on that path. The lower bound is nevertheless correct and can be repaired by a direct counting argument over unordered pairs: with fewer than n(n−1)/2 off-diagonal queries, some pair {i,j} has neither (i,j) nor (j,i) queried, and swapping columns i and j in any matching consistent with the leaf yields another consistent matching, contradicting uniqueness. As printed, however, the proof of D(Mn)=n(n−1)/2 is incomplete.
  2. [Section 4.1.1, Lemma 4.1] The claimed equivalence 'X[j] ≥ n − i if and only if MX(i,j)=1' is off by one. Since column j of MX is 0^{n−X[j]}1^{X[j]}, the condition MX(i,j)=1 is equivalent to X[j] > n−i (equivalently X[j] ≥ n−i+1), not X[j] ≥ n−i. Consequently, the simulation of a threshold query 'Is X[j] ≥ i?' should query entry (n−i+1,j), not (n−i,j). The lemma's conclusion is salvageable after this index correction, but the proof as stated contains a false equivalence and an out-of-range query for i=n.
  3. [Section 4.2, proof of Theorem 1.2 (quantum lower bound)] The application of Ambainis' adversary method (Lemma 4.3) is incomplete: the lemma requires two sets X,Y ⊆ D such that f(x)≠f(y) for every x∈X, y∈Y, but the proof defines only a relation R and verifies m,m',ℓ,ℓ' without specifying X and Y. Taking X=Y=Cn would violate the premise, since f is the identity. The proof can be fixed by taking X to be matrices in Cn whose column-weight permutation has even sign and Y to be those with odd sign, so that every adjacent-weight swap moves from one set to the other and the counts remain m=m'=n−1, ℓ=ℓ'=1. The Ω(n) lower bound is plausible, but the present derivation is not formally valid as written.
minor comments (5)
  1. [Section 2.2, final paragraph] The statement that all randomized and quantum upper bounds are in the 'weaker' expected-case model is not accurate for the quantum algorithm in Theorem 1.3, which relies on the bounded-error Grover subroutine from Lemma 2.2. The authors should either state that the quantum upper bounds are in the bounded-error model, or explain how the subroutines are made Las Vegas (for example, by verifying and repeating the search) so that the expected cost remains O(n log n).
  2. [Lemma 4.4] The proof should mention that after the search subroutine from Lemma 2.2 returns a candidate index i, the algorithm queries x_i and y_i to verify that they differ and to determine which of x≤y or x≥y holds; if the verification fails, the search is repeated. This ensures the stated expected cost and the correctness of the output.
  3. [Theorem 3.4] In the adversary calculation, the statement 'without loss of generality assume M1(i,j)=0' should be justified by noting that the minimum in the definition of CRA ranges over ordered pairs, so for every unordered pair of one-swap-away matrices there is an ordering in which the first matrix has a 0 at (i,j). When the first matrix has a 1 instead, θ is n/2, so the maximum of the two θ values is still at least n(n−1)/2.
  4. [Lemma 2.1 proof] The proof should be explicit that the constant c is chosen so that |R|^c < (2/3)|R| for all sufficiently large |R|; for small ranges the bound is subsumed by the big-Omega notation.
  5. [Equation (1) in Section 4.3] The 'naive upper bound' of O(Σ_j sqrt(n/j)) for the comparison sums is correct, but the text should explicitly note that Σ_{j=1}^n 1/sqrt(j) = Θ(sqrt(n)), so the comparison cost per pivot is O(n), to make the transition to the quicksort recurrence fully transparent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's bounds are established by explicit algorithms, adversary/counting lower bounds, and independently sourced external theorems, with no fitted parameters or self-referential reductions.

full rationale

The derivation chain is self-contained in the circularity-relevant sense. Theorem 1.1's deterministic bound is supported by an explicit greedy algorithm (Lemma 3.1) and a lower-bound argument via the all-0 leaf (Lemma 3.2). The randomized Θ(n^2) bound in Theorem 3.4 is proved directly using Aaronson's adversary theorem with a column-swap relation; the θ computation is arithmetic on the permutation-matrix domain, not a fitted parameter. The equivalences in Lemmas 4.1 and 4.2 are explicit bijections with query-by-query simulations, so transferring bounds between sorting and half-graph learning is not definitional circularity. Upper bounds in Theorems 1.2 and 1.3 are concrete algorithms with recurrences; lower bounds use counting (Lemma 2.1), Ambainis's adversary method (Lemma 4.3), and imported comparison lower bounds (HNS02, AGL+21, GJ22/GJ24), none of which are self-citations. No parameter is fitted to a subset of data and then renamed a prediction. The paper's own caveats—e.g., the unverified KMS98 claim in Section 1.1.3, the admitted failure to adapt HNS02 for Q(Cn) in Section 1.1.2, and Appendix B's O(n)-certificate observation—are correctness or provenance caveats, not circular steps. The only genuine defect is in Lemma 3.2's sentence 'Whenever A queries a pair on this path of the form (i,j) with i>j, we assume that it has also queried the pair (j,i) at no extra cost': this is an invalid proof step for a known deterministic bound, but it is a correctness issue rather than a circular reduction, and it does not affect the paper's central new randomized lower bound. Therefore the circularity score is 0.

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

The paper introduces no fitted constants or new entities. It relies on standard query-complexity definitions, adversary methods, and several external theorems (Aaronson, Ambainis, Boyer et al., HNS02, AGL+21, Goswami-Jacob). These are cited and accepted; the only internal assumption that is fragile is the free-symmetric-query step in Lemma 3.2, which is better treated as a proof gap.

assumptions (7)
  • standard math Aaronson's adversary method [Aar04, Theorem 5] gives R(f)=Ω(CRA(f)) for randomized query complexity.
    Used for the new randomized matching lower bound in Theorem 3.4; the theorem is quoted and cited, not proved in the paper.
  • standard math Ambainis' adversary method [Amb02] quantum lower bound applies to the Cn relation with ℓ=ℓ'=1.
    Used in the proof of Theorem 1.2 to obtain Q(Cn)=Ω(n); the method is cited as a lemma.
  • domain assumption Høyer-Neerbek-Shi [HNS02, Theorem 2] quantum comparison-sorting lower bound Ω(n log n) applies to the same-permutation row/column half-graph subfamily.
    Used in Lemma 4.6 for Q(Hn)=Ω(n log n); the transfer from their argument is asserted in one sentence, not derived in detail.
  • standard math Boyer et al. [BBHT98] quantum search finds a 1 in O(√(n/t)) expected queries when t entries are 1.
    Used in Lemma 2.2 and Lemma 4.4 as the comparison subroutine in the quicksort algorithms.
  • domain assumption van Apeldoorn et al. [AGL+21] proved Q(Mn)=Θ(n^{1.5}) for learning matchings.
    Used in Theorem 1.1 for the quantum matching bound; cited, not reproven in this paper.
  • domain assumption Goswami-Jacob [GJ22,GJ24b] give an O(n log n) randomized algorithm for perfectly interleaved bipartite sorting.
    Used via Lemma 4.2 to obtain the tight Θ(n log n) randomized upper bound for Hn; the algorithm itself is external to this paper.
  • domain assumption The hidden matrix in Hn is a row/column permutation of a lower triangular matrix, so rows are pairwise entrywise comparable and have distinct Hamming weights.
    This defining property of Hn is what makes Lemma 4.4's comparability promise hold in every comparison in Algorithm 1; the algorithm and its analysis depend on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity of learning matchings and half graphs via edge queries." pith.science (2026). https://pith.science/paper/A4CJQJOY

@misc{pith2026250703151,
  author       = {Pith},
  title        = {Pith review of: Complexity of learning matchings and half graphs via edge queries},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A4CJQJOY}},
  note         = {Machine review of arXiv:2507.03151}
}
abstract

The problem of learning or reconstructing an unknown graph from a known family via partial-information queries arises as a mathematical model in various contexts. The most basic type of access to the graph is via \emph{edge queries}, where an algorithm may query the presence/absence of an edge between a pair of vertices of its choosing, at unit cost. While more powerful query models have been extensively studied in the context of graph reconstruction, the basic model of edge queries seems to have not attracted as much attention. In this paper we study the edge query complexity of learning a hidden bipartite graph, or equivalently its bipartite adjacency matrix, in the classical as well as quantum settings. We focus on learning matchings and half graphs, which are graphs whose bipartite adjacency matrices are a row/column permutation of the identity matrix and the lower triangular matrix with all entries on and below the principal diagonal being 1, respectively. \begin{itemize} \item For matchings of size $n$, we show a tight deterministic bound of $n(n-1)/2$ and an asymptotically tight randomized bound of $\Theta(n^2)$. A quantum bound of $\Theta(n^{1.5})$ was shown in a recent work of van Apeldoorn et al.~[ICALP'21]. \item For half graphs whose bipartite adjacency matrix is a column-permutation of the $n \times n$ lower triangular matrix, we give tight $\Theta(n \log n)$ bounds in both deterministic and randomized settings, and an $\Omega(n)$ quantum lower bound. \item For general half graphs, we observe that the problem is equivalent to a natural generalization of the famous nuts-and-bolts problem, leading to a tight $\Theta(n \log n)$ randomized bound. We also present a simple quicksort-style method that instantiates to a $O(n \log^2 n)$ randomized algorithm and a tight $O(n \log n)$ quantum algorithm. \end{itemize}

Figures

Figures reproduced from arXiv: 2507.03151 by the authors.

Figure 1
Figure 1. Illustration of a single iteration of the [PITH_FULL_IMAGE:figures/full_fig_p015_1.png] view at source ↗
Figure 2
Figure 2. Depiction of inductive process in the Proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p021_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 32 canonical work pages

  1. [1]

    Lower bounds for local search by quantum arguments

    Scott Aaronson. Lower bounds for local search by quantum arguments. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , pages 465--474, 2004

    work page 2004

  2. [2]

    Hasan Abasi and Nader H. Bshouty. On learning graphs with edge-detecting queries. In Algorithmic Learning Theory, ALT , 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 Journal on Computing , 33(2):487--501, 2004. Preliminary version in FOCS'02

    work page 2004

  4. [4]

    Learning a hidden graph using o(logn) queries per edge

    Dana Angluin and Jiang Chen. Learning a hidden graph using o(logn) queries per edge. J. Comput. Syst. Sci. , 74(4):546--556, 2008. Preliminary version in COLT'04

    work page 2008

  5. [5]

    Quantum algorithms for matrix scaling and matrix balancing

    Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter, and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing. In 48th International Colloquium on Automata, Languages, and Programming, ICALP , volume 198 of LIPIcs , pages 110:1--110:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2021

    work page 2021

  6. [6]

    Combinatorial search

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

    work page 1988

  7. [7]

    All classical adversary methods are equivalent for total functions

    Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs, and Aleksejs Zajakins. All classical adversary methods are equivalent for total functions. ACM Trans. Comput. Theory , 13(1):7:1--7:20, 2021. Preliminary version in STACS'18

    work page 2021

  8. [8]

    Quantum lower bounds by quantum arguments

    Andris Ambainis. Quantum lower bounds by quantum arguments. J. Comput. Syst. Sci. , 64(4):750--767, 2002. Preliminary version in STOC'00

    work page 2002

Show all 34 references
  1. [9]

    Tight bounds on quantum searching

    Michel Boyer, Gilles Brassard, Peter H yer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics , 46(4-5):493--505, 1998

    1998

  2. [10]

    Network discovery and verification

    Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Mat Mihal'ak, and L Shankar Ram. Network discovery and verification. IEEE Journal on selected areas in communications , 24(12):2168--2181, 2006

    2006

  3. [11]

    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. arXiv preprint arXiv:2306.05979 , 2023

    2023 arXiv

  4. [12]

    Combinatorial search on graphs motivated by bioinformatics applications: A brief survey

    Mathilde Bouvel, Vladimir Grebinski, and Gregory Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. In Graph-Theoretic Concepts in Computer Science: 31st International Workshop, WG 2005, Metz, France, June 23-25, 2005, Revised Se...

    2005

  5. [13]

    Complexity measures and decision tree complexity: a survey

    Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci. , 288(1):21--43, 2002

    2002

  6. [14]

    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. Preliminary version in STOC'08

    2010

  7. [15]

    Introduction to algorithms

    Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms . MIT press, 2022

    2022

  8. [16]

    Universal sorting: Finding a DAG using priced comparisons

    Mayank Goswami and Riko Jacob. Universal sorting: Finding a DAG using priced comparisons. CoRR , abs/2211.04601, 2022

    2022 arXiv

  9. [17]

    An algorithm for bichromatic sorting with polylog competitive ratio

    Mayank Goswami and Riko Jacob. An algorithm for bichromatic sorting with polylog competitive ratio. In 15th Innovations in Theoretical Computer Science Conference, ITCS , volume 287 of LIPIcs , pages 56:1--56:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2024

    2024

  10. [18]

    On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting

    Mayank Goswami and Riko Jacob. On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024 , volume 317 of LIPIcs , pages 23:1--23:...

    2024

  11. [19]

    Optimal query bounds for reconstructing a hamiltonian cycle in complete graphs

    Vladimir Grebinski and Gregory Kucherov. Optimal query bounds for reconstructing a hamiltonian cycle in complete graphs. In Fifth Israel Symposium on Theory of Computing and Systems, ISTCS , pages 166--173. IEEE Computer Society, 1997

    1997

  12. [20]

    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. Preliminary version in ESA'97

    2000

  13. [21]

    A fast quantum mechanical algorithm for database search

    Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pages 212--219, 1996

    1996

  14. [22]

    Quantum complexities of ordered searching, sorting, and element distinctness

    Peter H yer, Jan Neerbek, and Yaoyun Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica , 34(4):429--448, 2002

    2002

  15. [23]

    Randomized communication and implicit graph representations

    Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev. Randomized communication and implicit graph representations. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1220--1233, 2022

    2022

  16. [24]

    Matching nuts and bolts in o(n log n) time

    J \' a nos Koml \' o s, Yuan Ma, and Endre Szemer \' e di. Matching nuts and bolts in o(n log n) time. SIAM J. Discret. Math. , 11(3):347--372, 1998

    1998

  17. [25]

    Near-linear query complexity for graph inference

    Sampath Kannan, Claire Mathieu, and Hang Zhou. Near-linear query complexity for graph inference. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 42 , pages 773--784. Springer, 2015

    2015

  18. [26]

    Graph reconstruction via MIS queries

    Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph reconstruction via MIS queries. In 16th Innovations in Theoretical Computer Science Conference, ITCS , volume 325 of LIPIcs , pages 66:1--66:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025

    2025

  19. [27]

    Reconstructing random graphs from distance queries

    Michael Krivelevich and Maksim Zhukovskii. Reconstructing random graphs from distance queries. arXiv preprint arXiv:2404.18318 , 2024

    2024 arXiv

  20. [28]

    Quantum algorithms for learning a hidden graph

    Ashley Montanaro and Changpeng Shao. Quantum algorithms for learning a hidden graph. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC , volume 232 of LIPIcs , pages 1:1--1:22. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022

    2022

  21. [29]

    Graph reconstruction via distance oracles

    Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles. In International Colloquium on Automata, Languages, and Programming , pages 733--744. Springer, 2013

    2013

  22. [30]

    A simple algorithm for graph reconstruction

    Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. Random Structures & Algorithms , 63(2):512--532, 2023

    2023

  23. [31]

    Quantum computation and quantum information , volume 2

    Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information , volume 2. Cambridge university press Cambridge, 2001

    2001

  24. [32]

    Gregory J. E. Rawlins. Compared to what? - an introduction to the analysis of algorithms . Principles of computer science series. Computer Science Press, 1992

    1992

  25. [33]

    Reconstruction and verification of chordal graphs with a distance oracle

    Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theoretical Computer Science , 859:48--56, 2021

    2021

  26. [34]

    Probabilistic computations: Toward a unified measure of complexity

    Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science ( SFCS 1977) , pages 222--227. IEEE Computer Society, 1977

    1977

Pith tools

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