{"id":"5b172ea8-b444-48c2-88a0-003a4e3ffc1c","arxiv_id":"2511.04058","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For a planted 2-factor on a random δn vertices in G(n,λ/n), almost-exact recovery is possible iff λ < 1/(√(2δ)+√(1−δ))², and a polynomial-time algorithm achieves this bound.","lead":"This math paper pins down the exact amount of background noise at which a hidden collection of cycles in a random graph can still be recovered, and it gives a polynomial-time algorithm that succeeds right up to that limit. The result is a rare example where the information-theoretic and computational thresholds coincide, in contrast to the planted clique problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 is missing an upper bound on |H|: E[|H|] ≤ δn+o(n) is required by Lemma 4.3 but not proved by Lemma 4.4.","rationale":"The reader identified Lemma 2.1 / Kotzig's alternating Eulerian circuit decomposition as the weakest assumption. I examined that step: the four vertex types in H*ΔH all admit partitions with parts of size at most half the degree, so the hypotheses of Kotzig's theorem are met; the decomposition is not a genuine weak point. The actual soft spot is in the algorithmic proof: Theorem 4.1 claims a polynomial-time estimator achieving almost exact recovery, but its proof combines Lemma 4.3 with Lemma 4.4, and Lemma 4.4 establishes only a lower bound on |H|. Lemma 4.3's hypothesis is E[|H|] = δn − o(n), i.e. it needs |H| to be close to δn from both sides. The algorithm's updates are monotone increasing in |H| and can consume unplanted trails, so without an explicit upper bound one cannot rule out |H| noticeably above δn. The gap is probably patchable: the excess-counting machinery already controls the total excess of all trails in the graph, and the triangle inequality |HΔH*| ≥ ||H|−δn| should force E[|H|] ≤ δn + O(1) once the excess bound is applied to the algorithm's actual H. But this step is not in the paper, and as written the implication 'Lemma 4.4 + Lemma 4.3 ⇒ Theorem 4.1' does not go through. Since the result is very likely correct and the fix is local, I recommend CONDITIONAL acceptance rather than rejection: require the authors to supply the missing upper-bound argument (or adjust Lemma 4.3's statement to include the asymmetric version) before the algorithmic claim is regarded as proven.","tokens_in":37536,"tokens_out":43106,"duration_ms":353592,"concrete_test":"Attempt to close the gap by deriving E[|H|] ≤ δn + o(n) for Algorithm 4's output as follows: combine Lemma 4.3's bound E[Σ ex(P_i)] ≤ C + o(n) (valid for any H with o(n) degree-1 vertices and degree ≤2) with the identity |HΔH*| = (1/ε)(Σ ex(P_i) + 1/2(δn − |H|)) and the trivial inequality |HΔH*| ≥ ||H|−δn|; algebra would force E[|H|]−δn ≤ O(1). If this derivation is invalid, simulate Algorithm 4 on G(n,λ/n) with δ=0.1, λ=0.5 (below threshold) and n=10^5 and measure whether |H|−δn = Ω(n) with non-negligible probability across independent trials.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 4.3 is the statistical engine for the efficient estimator: it concludes E[|H*ΔH|] = o(n) under the assumptions E[|H|] = δn − o(n) and E[#degree-1 vertices] = o(n). Lemma 4.4 proves only |H| ≥ δn − O(n/√log n) and at most 2n/√log n degree-1 vertices; it gives no matching upper bound on |H|. The algorithm only ever increases |H| (each XOR update has positive net gain), and it can apply cost-free or cost-effective updates using unplanted trails. A priori, the output could contain many more than δn edges, e.g. by absorbing unplanted paths of length < log n that connect existing degree-1 vertices. If that happens with non-negligible probability, E[|H|] could exceed δn by Ω(n), and then E[|HΔH*|] ≥ |E[|H|]−δn| = Ω(n), contradicting almost exact recovery. The text jumps from Lemma 4.4 to Theorem 4.1 without supplying this upper bound. This is a missing support in the proof of the algorithmic half of Theorem 1.1. (The information-theoretic threshold itself is not affected.) Note also that the reader's flagged concern about Kotzig's theorem appears to be satisfiable: each vertex class has label classes of size at most half the degree, so [16, Thm. 1] applies. The algorithm upper bound is the more serious gap.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the planted cycles model G(n, λ, δ), where a uniformly random set of δn vertices carries a uniformly random 2-factor H*, and all remaining pairs are present independently with probability λ/n. The main result, Theorem 1.1, asserts a sharp almost-exact-recovery threshold at λ_c = (√(2δ)+√(1−δ))^{−2}: below λ_c, almost exact recovery is possible and is achieved by a polynomial-time algorithm; above λ_c, no estimator can do better than constant error. The proof has three parts: a generating-function count of alternating (a,b)-trails to prove achievability (§2); a branching-process and sprinkling construction of many balanced cycles to prove impossibility (§3); and a greedy algorithm based on short trails to prove the algorithmic claim (§4).","tokens_in":37901,"tokens_out":16041,"duration_ms":129900,"significance":"If the results are correct, this is a substantial contribution: a sharp information-theoretic threshold for recovery of a planted 2-factor with unknown support, and—strikingly—no statistical–computational gap, in contrast to the planted clique problem. The generating-function technique for counting alternating trails is elegant and self-contained, and the impossibility argument via path trees and sprinkling is technically sophisticated. The algorithmic section is also ambitious: it gives a concrete polynomial-time procedure with a detailed structural analysis. The main theorem, however, is not yet fully established because of a gap in the proof of the algorithmic half.","major_comments":[{"comment":"Lemma 4.4 only proves a lower bound on the output size, |H| ≥ δn − O(n/√log n), together with a bound on the number of degree-1 vertices. Lemma 4.3, which is the statistical engine for the efficient estimator, requires the stronger assumption E[|H|] = δn − o(n). No matching upper bound on |H| is supplied. The algorithm's updates search over all short trails in G, not only over trails contained in HΔH*, so after H reaches the desired size it can in principle absorb unplanted paths: a cost-free update can add an unplanted path joining two degree-1 vertices of H, increasing |H| without increasing the number of degree-1 vertices, and a cost-effective update can add a new unplanted path of length at least √log n. The degree-1 budget in Lemma 4.4 does not rule out Ω(n) overshoot, because each cost-effective update can add up to log n edges and there are up to n/√log n such updates. Thus the pr","section":"Theorem 4.1 / Lemmas 4.3–4.4"}],"minor_comments":[{"comment":"The parameter order is inconsistent: the statement reads G∼G(n, δ, λ), while the model in Definition 1.1 is G(n, λ, δ).","section":"Theorem B.1"},{"comment":"In the proof of Lemma 3.9, the text refers to “Proposition 3.8” when the statement cited is Lemma 3.8.","section":"Lemma 3.9"},{"comment":"The pruning condition says “reachable by a path of length at most 2m*”, while the path layers are non-shortcutted (m*,m*)-paths of length exactly 2m*. Please clarify whether the pruning radius is intentionally larger than the path length, and reconcile with the domination argument in Lemma 3.8.","section":"Algorithm 1"},{"comment":"“choose a set of δn2 vertices” appears to be a typo for “δn vertices”; the surrounding text and the exponent in the abstract use δn.","section":"Definition 1.1"}],"recommendation":"major_revision","confidential_remarks":"The missing upper bound on the output size of Algorithm 4 is a genuine gap, but it is local to §4 and may be fixable by adding a termination condition (e.g., stop when |H| reaches δn) or by proving that the greedy updates cannot overshoot by more than o(n). The Kotzig-theorem concern raised during review appears to be satisfiable, since the label classes in Lemma 2.1 have size at most half the vertex degree. I would encourage the editor to invite a revision addressing the algorithmic gap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper before recommending it: the information-theoretic threshold for planted 2-factor recovery looks right and is a genuine advance, but the proof of the polynomial-time half has a hole that the authors may be able to patch. Theorem 1.1 claims both a sharp threshold and an efficient algorithm with no statistical-computational gap. The threshold for δ<1 (unknown vertex support) is new, and the generating-function characterization in §2 is elegant. The achievability proof (Theorem 2.4) is self-contained and convincing: the two-parameter generating function in (2.4) and the elementary algebra in Lemma 2.3 cleanly identify the threshold. The impossibility proof (§3) is heavy but follows a known branching-process-plus-sprinkling template, and I see no red flags there beyond the usual complexity. So the information-theoretic result is in good shape.\n\nThe soft spot is Theorem 4.1. Lemma 4.3, the statistical engine for the algorithm, assumes E[|H|] = δn − o(n) — an upper bound as well as a lower bound. Lemma 4.4 only proves |H| ≥ δn − O(n/√log n) and bounds the number of degree-1 vertices; nowhere does the paper prove |H| ≤ δn + o(n). Since the algorithm only XORs trails that increase |H|, it can overshoot, and absorbing unplanted paths or small cycles would make |H| larger than δn by a constant fraction. If that happens, Lemma 4.3 doesn't apply and E[|HΔH*|] ≥ Ω(n). The text simply jumps from Lemma 4.4 to Theorem 4.1. This is a missing support in the algorithmic half. It is not fatal to the threshold itself, but it means the \"no computational-statistical gap\" headline is not yet proven as written. A patch might come from subcriticality (background graph has O(1) cycles, so overshoot may be o(n)), but that argument is not in the paper. The Kotzig concern flagged earlier is satisfiable — the label classes in Lemma 2.1 are at most half the degree, so [16] applies.\n\nWho should read this: anyone working on planted structures in sparse random graphs will want the threshold and the generating function technique. It deserves a serious referee, but I'd send it back for major revision rather than accept as is. If the authors close the |H| upper bound, this becomes a strong paper.","headline":"Sharp threshold result is likely correct, but the polynomial-time claim has a missing upper bound on |H| and needs a patch.","tokens_in":38374,"tokens_out":7160,"would_cite":true,"duration_ms":59097,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","60C05","60J80"],"pacs":[],"model":"deepseek-v4-flash","headline":"In the planted cycles model, almost exact recovery succeeds exactly below a sharp threshold—and a polynomial-time algorithm attains it; above the threshold, recovery is impossible.","keywords":["random graphs","planted cycles","phase transitions","almost exact recovery","generating functions","branching processes","2-factor","Erdős–Rényi"],"falsifier":"Simulate the model at δ=2/3 with λ slightly below and above 1/3, and compute the minimum achievable symmetric difference over all 2-factors (or run the paper's algorithm). The claim predicts an abrupt transition from error o(1) to error Ω(1) exactly at λ=1/3, with polynomial-time success below the threshold. A direct count of balanced (a,a)-circuits in the observed graph should show bounded expectation below the threshold and divergence above it.","tokens_in":37434,"feed_emoji":"🔄","tokens_out":3531,"duration_ms":30465,"temperature":0.7,"pith_summary":"The paper studies a random graph model in which a hidden collection of vertex-disjoint cycles (a 2-factor) is planted on a randomly chosen δn vertices of an Erdős–Rényi graph with edge probability λ/n. It identifies a single constant threshold, λ* = 1/(√(2δ)+√(1−δ))², that separates two regimes. Below λ*, every 2-factor close to the planted one can be recovered up to a vanishing fraction of edges, and the paper gives a polynomial-time greedy algorithm that does so. Above λ*, no algorithm—however powerful—can do better than constant error. The result is a sharp threshold with no gap between statistical possibility and computational tractability, in contrast to the planted clique problem.","feed_headline":"Planted-cycle recovery: one formula separates possible from impossible","feed_subtitle":"A polynomial-time algorithm succeeds whenever information theory permits, unlike planted clique.","key_machinery":"The difference graph between the planted 2-factor and any competing 2-factor decomposes into alternating (a,b)-circuits via a black-box theorem on alternating Eulerian circuits. The generating function g(x,y) = Σ_{k≥1} (2x/(1−x) · δλy/(1−(1−δ)λy))^k counts the expected number of such trails; convergence of this series on the curve xy=1 with 0