{"id":"4e57f11e-4f26-4b11-aa6b-171af0ee0290","arxiv_id":"2507.03151","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Tight edge-query bounds are proven for learning matchings (deterministic n(n-1)/2, randomized Θ(n^2)) and half graphs (Θ(n log n) classically for column-permuted, Θ(n log n) quantum in general), with half-graph learning reduced to sorting problems.","lead":"This paper determines how many yes/no edge queries are needed to identify a hidden matching or half graph. It finds tight deterministic, randomized, and quantum bounds and connects half-graph learning to sorting problems like nuts-and-bolts.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.2's lower-bound proof assumes free symmetric queries; this is false as stated, but the bound is repairable by direct counting, so the central randomized result R(Mn)=Θ(n²) is unaffected.","rationale":"The reader's weakest assumption is accurate: the sentence in Section 3.1 is not a valid wlog reduction. However, the deterministic lower bound is an already-known result (Aigner 1988), and the paper's genuinely new matching bound, R(Mn)=Θ(n²), is proved by a separate Aaronson-adversary argument in Theorem 3.4 that I checked and found sound. The half-graph equivalences are also sound up to a fixable off-by-one in the threshold-query mapping in Lemma 4.1, which does not change the complexity conclusions. Thus the appropriate verdict remains conditional on a proof repair, matching the reader's CONDITIONAL verdict.","tokens_in":17356,"tokens_out":37913,"duration_ms":412434,"concrete_test":"Rewrite the proof of Lemma 3.2 without the 'at no extra cost' symmetric-query assumption, replacing it with the following count: fewer than n(n−1)/2 off-diagonal queries leave some unordered pair {i,j} with neither (i,j) nor (j,i) queried, and since the all-0 path queries no diagonal, flipping the 2×2 block on rows/columns i,j gives a second matching that reaches the same leaf. Then check that the repaired proof is the only change needed in Section 3.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The written proof of D(Mn)=n(n−1)/2 in Lemma 3.2 contains a genuine invalid step: it asserts that whenever the all-0 path queries (i,j) with i>j, the algorithm has also queried (j,i) 'at no extra cost.' An arbitrary deterministic algorithm need not make symmetric queries, so an unqueried above-diagonal entry does not by itself certify an unqueried 2×2 block. This step can be replaced by a valid counting argument: with fewer than n(n−1)/2 off-diagonal queries, the queried entries cover fewer than all n(n−1)/2 unordered pairs {i,j}, so some pair has neither (i,j) nor (j,i) queried; since no diagonal entry is queried on the all-0 path, the corresponding 2×2 block can be flipped to produce a second matching reaching the same leaf. Hence the lower bound is correct, but the proof as printed must be repaired. This does not affect the paper's central new claim R(Mn)=Θ(n²), whose Aaronson-adversary argument is sound as far as I can verify; it is a correctness defect in a known result that the authors included for completeness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17542,"tokens_out":24597,"duration_ms":258256,"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":[{"comment":"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.","section":"Section 3.1, Lemma 3.2"},{"comment":"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.","section":"Section 4.1.1, Lemma 4.1"},{"comment":"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.","section":"Section 4.2, proof of Theorem 1.2 (quantum lower bound)"}],"minor_comments":[{"comment":"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).","section":"Section 2.2, final paragraph"},{"comment":"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.","section":"Lemma 4.4"},{"comment":"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.","section":"Theorem 3.4"},{"comment":"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.","section":"Lemma 2.1 proof"},{"comment":"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.","section":"Equation (1) in Section 4.3"}],"recommendation":"major_revision","confidential_remarks":"The three major issues are all repairable and do not affect the paper's central new claim, the randomized lower bound R(Mn)=Θ(n²), whose adversary calculation appears sound. The off-by-one in Lemma 4.1 and the missing adversary sets in Theorem 1.2 are localized fixes. The deterministic matching lower bound is a known result (Aigner 1988), so the flawed proof is a correctness defect rather than a novelty concern. The paper fits the journal and will be a solid contribution after revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new result here is the randomized Omega(n^2) lower bound for learning matchings via edge queries, which matches the deterministic upper bound and closes that case. The half-graph results are also nice: the equivalences to threshold sorting and perfectly interleaved bipartite sorting are exact bijections, not analogies, and the quicksort-style algorithms are genuinely simple. Replacing the comparison subroutine with Grover to get a tight quantum bound is a clean trick.\n\nThe paper is honest about what is new and what comes from prior work. The adversary argument in Theorem 3.4 is short and correct as far as I can tell. The upper bounds for column-permuted half graphs via binary search and the counting lower bounds are standard but correctly executed. The quicksort analysis is careful, and the recurrence for the randomized O(n log^2 n) bound is worked out.\n\nThe main blemish is Lemma 3.2, the deterministic lower bound for matchings. The proof assumes that querying (i,j) with i>j also queries (j,i) at no extra cost. That is false for an arbitrary deterministic algorithm, and the stress-test is right about the gap. However, the bound itself is correct and known (Aigner 1988), and there is a simple repair: if fewer than n(n-1)/2 off-diagonal entries are queried, the forbidden set is too small to force a unique perfect matching, so the all-0 path cannot identify a unique matching. This is a minor correctness defect in a completeness proof, not in any new claim.\n\nThe randomized Omega(n^2) lower bound is completely separate and stands on Aaronson's adversary method. The half-graph equivalences in Section 4 are also independent of the flawed lemma. Several quantum bounds rely on external theorems that I did not verify in detail, but the citations (AGL+21, HNS02, GJ22/24) match the statements well enough.\n\nThis paper is for researchers working on graph reconstruction or on oracle-model sorting problems. It deserves a serious referee, and I would send it to peer review. The authors should be asked to fix Lemma 3.2, either with the counting argument or by citing Aigner. The new results are solid enough that this is a conditional accept, not a reject.","headline":"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.","tokens_in":18113,"tokens_out":4532,"would_cite":true,"duration_ms":49907,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Learning a hidden matching with edge queries requires n(n-1)/2 queries deterministically and Theta(n^2) even with randomization.","keywords":["edge queries","graph reconstruction","query complexity","matchings","half graphs","randomized lower bounds","quantum query complexity","nuts-and-bolts sorting"],"falsifier":"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.","tokens_in":17127,"feed_emoji":"🔍","tokens_out":8053,"duration_ms":85772,"temperature":0.7,"pith_summary":"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.","feed_headline":"Even randomized algorithms need quadratic edge queries for matchings","feed_subtitle":"The same edge-query model solves half graphs in Θ(n log n) queries via a sorting equivalence.","key_machinery":"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.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"Gives the classical deterministic n(n-1) bound for learning a matching without a fixed bipartition, which the paper adapts and proves in its setting.","marker":"[Aig88]"},{"why":"Supplies the classical adversary theorem used to prove the randomized lower bound R(M_n)=Omega(n^2).","marker":"[Aar04]"},{"why":"Provides the quantum query bounds that yield Q(M_n)=Theta(n^1.5) for learning matchings.","marker":"[AGL+21]"},{"why":"Provides the adversary method used for quantum lower bounds on column-permuted and general half graphs.","marker":"[Amb02]"},{"why":"Yao's minimax principle underlies the range-counting lower bound behind the deterministic and randomized Theta(n log n) bounds for column-permuted half graphs.","marker":"[Yao77]"},{"why":"Gives the O(n log n) algorithm for perfectly interleaved bipartite sorting that transfers to randomized and quantum upper bounds for general half graphs.","marker":"[GJ22]"},{"why":"Provides the quantum comparison-based sorting lower bound of Omega(n log n) used to show Q(H_n)=Omega(n log n).","marker":"[HNS02]"}],"fun_headline_variants":["Randomized edge queries for matchings stay quadratic","Half graphs tamed in n log n edge queries via sorting","Nuts-and-bolts connection yields tight half graph queries","Edge queries: matchings quadratic, half graphs n log n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Randomized edge queries for matchings stay quadratic","Half graphs tamed in n log n edge queries via sorting","Nuts-and-bolts connection yields tight half graph queries","Edge queries: matchings quadratic, half graphs n log n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001084,"raw_usage":{"total_tokens":4605,"prompt_tokens":1088,"completion_tokens":3517,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":704,"completion_tokens_details":{"reasoning_tokens":3450}},"tokens_in":704,"tokens_out":3517,"duration_ms":31315,"temperature":1.0,"reasoning_tokens":3450,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:20:07.846804+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}