{"id":"5e0f928a-e4fd-421a-9479-55f65311b95a","arxiv_id":"1908.07493","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the noisy corruption detection game on constant-degree expanders, Θ(n log n) queries are necessary and sufficient when the truthful majority is small, while O(n) queries suffice when the truthful fraction is at least 1/2+δ.","lead":"This paper settles the noisy version of a graph query game, counting the queries needed to find almost all truthful vertices when some vertices lie and answers are random. It proves a tight Θ(n log n) bound when the truthful majority is small, and a linear O(n) bound when truth-tellers have a robust majority.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound proof does not control how the adaptive query process couples the obscured set O with T; the claim that many vertices are obscured is not established.","rationale":"The reader identified the same load-bearing weakness: Lemma 2.3 is applied to an obscured set O that is not independent of the random partition T/B. My check sharpens this: the dependence enters before Lemma 2.3, because the definition of O is a data-dependent stopping event. If the proof's estimate of the number of obscured vertices fails, the entire reduction to the fixed-O lemma collapses. I do not claim the theorem is false; the lower bound may be repairable with a more careful martingale or non-adaptive coupling argument. But the written proof has a real gap in its central step, so the paper should not be accepted without revision. Since the reader's CONDITIONAL verdict already requires addressing this dependence, my read does not change the verdict. I therefore set verdict_should_be to UNCHANGED and agree with the reader's weakest_assumption.","tokens_in":4926,"tokens_out":27944,"duration_ms":305637,"concrete_test":"Simulate the Section 2 model on a degree-3 expander with n = 10^4, β = 0.1, ε = 0.01, using the adaptive player strategy that queries each vertex about a fixed neighbor until it has received both a truthful-looking and a corrupt-looking report from that vertex (capped at c log n queries), then moves on. Record, over many repetitions, the empirical value of P(v obscured | M_v ≤ c log n) and the realized size of O. If this conditional probability is o(n^{-β/2}) or the total |O| is less than n^{1-β} with non-negligible probability, the aggregation step in Theorem 2.2 is invalid as written; a positive result would instead indicate the estimate survives for this rule.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2.2 rests on the set O of obscured vertices and on Lemma 2.3, which is proved for a fixed O under a uniformly random partition of V into T and B. In the actual game O is not fixed: a vertex is obscured exactly when every query involving it was answered by the 2ε coin, and the number M_v of queries involving v is a stopping time chosen adaptively from the observed answer bits, which themselves depend on T. The proof asserts that a vertex involved in at most c log n queries is obscured with probability at least n^{-β/2}, but this conditional statement is not justified: the event {M_v ≤ c log n} can be selected by stopping after an answer that makes the all-coin event false, so P(v obscured | M_v=m) can fall far below (2ε)^m. Hence the expected number of obscured vertices need not be ≥ (1/2)n^{1-β/2}, and the passage to the subgraph G' = G - O with |O| ≥ n^{1-β} is not established. Moreover, since the query sequence is a function of T and the coin flips, the distribution of T conditional on O is not the uniform partition required by Lemma 2.3. The 1/2 + o(1) success bound therefore lacks a proof that the player cannot, by adaptively avoiding coin-flipped vertices, retain information about T on more than a negligible fraction of U.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a noisy version of the corruption detection model of Alon, Mossel, and Pemantle. The player queries vertices about their neighbors; truthful vertices answer correctly with probability 1-eps and otherwise with a fair coin, and corrupt vertices lie with probability 1-2eps and otherwise answer with a fair coin. The main results are: (i) Theorem 2.2, a lower bound Omega(n log n) on the number of queries needed to identify most vertices when |T|-|B| <= n^{1/2-beta}; (ii) Theorem 3.1, an O(n)-query algorithm when |T|=(1/2+delta)n on a delta-excellent expander, outputting a set with symmetric difference at most 6 delta n from T. The upper bound for the robust-majority case uses majority amplification followed by a search for two large sets with few conflicting edges. The lower bound is proved by an adversarial noise strategy: with high probability many vertices are 'obscured' (all answers involving them are pure coin flips), and after discarding those answers the problem reduces to a noiseless setting where the player cannot determine the majority by symmetry.","tokens_in":5186,"tokens_out":17688,"duration_ms":157095,"significance":"If correct, the results answer a natural question from Alon, Mossel, and Pemantle. The qualitative transition between Theta(n log n) and O(n) queries is appealing, and the upper bound's reduction to the deterministic noiseless case is elegant. The lower bound's obscuring-vertices idea is intuitive and, in a non-adaptive setting, would give a clean argument. However, as detailed below, the proof of the lower bound has a serious gap concerning adaptive queries, and the proof of the upper bound contains an unjustified inequality. These issues affect the two main theorems, so the significance of the paper depends on whether they can be repaired.","major_comments":[{"comment":"The proof defines an obscured vertex as one for which every query involving it is answered by a coin flip, and then states: 'If c is sufficiently small, a vertex that is involved in at most c log(n) queries has a probability at least n^{-beta/2} of being obscured.' This is a conditional probability statement with the condition M_v <= c log n, where M_v is the number of queries involving v. In the actual game, the player's queries are adaptive, so M_v is a stopping time with respect to the observed answers, which themselves depend on the coin flips and on T. The event {M_v <= m} can therefore be correlated with the event that all answers involving v are coin flips; a strategy that queries v until a non-coin answer appears makes the conditional probability of obscuring zero. Consequently, the claimed lower bound on the expected number of obscured vertices does not follow. Moreover, the set O of obscured vertices is a function of the adaptive query process, so O and T are correlated; the conditional distribution of T given O is not the uniformly random partition required by Lemma 2.3. The reduction to the subgraph G' = G - O and the subsequent symmetry argument therefore do not establish the claimed 1/2 + o(1) success probability. This is a load-bearing gap in the main lower bound.","section":"Section 2, proof of Theorem 2.2"},{"comment":"The final chain 'Y has fewer than 3 delta n corrupt vertices. By assumption, |X cap T| >= |Y cap T|, so |X Delta T| <= |Y Delta T| and |(X cup Y) Delta T| <= 2|Y Delta T| <= 6 delta n' is not justified. The preceding argument bounds only |Y \\ T| (the number of corrupt vertices in Y), not the full symmetric difference |Y Delta T| = |Y \\ T| + |T \\ Y|. Since |X cup Y| = |T|, the term |T \\ Y| equals |X cap T| + |T \\ (X cup Y)|, which can be large; for example, if delta is small and Y is mostly truthful, |T \\ Y| is of order n/4. Thus the inequality |Y Delta T| <= 3 delta n does not follow, and the stated bound |(X cup Y) Delta T| <= 6 delta n is not proven. The argument appears to yield at best |(X cup Y) Delta T| < 12 delta n. This is a flaw in the proof of the stated theorem, though the qualitative O(n) query claim is likely unaffected and the constant can presumably be adjusted.","section":"Section 3, proof of Theorem 3.1"}],"minor_comments":[{"comment":"The abstract contains a formatting artifact: 'corru ption' appears with an unwanted space. Please fix.","section":"Abstract and Introduction"},{"comment":"The proof refers to 'a simple computation (or the local central limit theorem)' to bound the probability that | |T1 cap O| - |B cap O| | <= n^{1/2-beta}. Since this is a key step, a brief indication of the computation or an explicit reference would improve rigor.","section":"Lemma 2.3"},{"comment":"The algorithm in Section 3 is described as taking exponential time, but the theorem is stated only in terms of query complexity. It would be helpful to state explicitly in Theorem 3.1 that the overhead is exponential, so that readers do not infer a polynomial-time guarantee.","section":"Section 4, Discussion"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound gap is the central issue. If the author can supply a rigorous argument that handles the adaptive dependence of the obscured set O on T, the paper could be acceptable. The upper-bound constant issue appears easily repairable. I recommend major revision rather than rejection, but the burden is on the author to provide a complete proof of Theorem 2.2 as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read of Alweiss's noisy corruption detection paper. The headline result—Θ(n log n) queries for the balanced-to-near-balanced case, O(n) for the (1/2+δ)n case—is exactly the sort of thing the AMP question was waiting for. Theorem 3.1, the robust-majority upper bound on δ-excellent expanders, is clean and I think correct. The reduction to the noiseless theorem in Section 2 is elegant, and the symmetry argument in Lemma 2.3 is fine on its own.\n\nThe problem is the lower bound proof, and it's load-bearing. The proof wants to say that many vertices are 'obscured'—every query involving them gets the 2ε fair coin. The claim is that a vertex involved in at most c log n queries is obscured with probability at least n^{+β/2}. But the number of queries involving a vertex is an adaptively chosen stopping time, not a fixed bound. The player can stop querying a vertex after receiving a deterministic answer, which makes the event 'few queries' negatively correlated with the event 'all coins.' So the conditional probability can be much smaller than (2ε)^m. The proof doesn't handle this, and the set O of obscured vertices is therefore not guaranteed to be large. On top of that, O is a function of the query process, which is a function of T, so conditioning on O breaks the uniform-prior assumption needed for Lemma 2.3. The stress-test note I got spelled this out in detail, and on reading the paper I think it lands.\n\nThe acknowledgment thanks Mark Sellke for 'drawing attention to conditional issues in an earlier draft,' so the issue is at least partially known. But the current text still asserts the unjustified step. It may be repairable—a careful martingale or a different adversarial strategy could yield the same Ω(n log n) bound—but it's not there yet.\n\nWhat's genuinely good: the O(n) robust-majority algorithm is rigorous and the constants check out. The paper is well-written, short, and honest about what's a reduction and what's new. The lower-bound technique, once fixed, would be a real contribution.\n\nFor you: I'd say this deserves a serious referee, not a desk reject. The central question is whether the lower bound can be repaired. If yes, it's a nice answer to AMP. If no, the O(n) result still stands but the main novelty is in question. I probably wouldn't cite the lower bound until it's fixed. Worth discussing in reading group if you want to walk through the stopping-time issue.","headline":"The upper bound is solid and the lower bound is a good idea, but the proof of the Ω(n log n) claim has a real conditional-probability gap that needs to be fixed before that result can stand.","tokens_in":5730,"tokens_out":9890,"would_cite":false,"duration_ms":100913,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"In noisy graph corruption detection, a slender truthful majority costs n log n queries, while a constant majority costs linear queries.","keywords":["corruption detection","query complexity","expander graphs","noisy queries","threshold phenomenon","lower bounds","graph algorithms"],"falsifier":"Simulate the lower-bound adversary on a constant-degree expander with $|T|-|B|=1$ and let the player use an adaptive strategy that spends $o(n\\log n)$ queries; if the player's success probability exceeds $1/2+o(1)$, the claimed $\\Omega(n\\log n)$ lower bound is false.","tokens_in":4729,"feed_emoji":"🕵️","tokens_out":17990,"duration_ms":156183,"temperature":0.7,"pith_summary":"This paper studies a one-player game on a graph in which each vertex is either truthful or corrupt; the player may ask any vertex about the status of a neighbor, and truthful vertices answer correctly with probability $1-\\varepsilon$ while corrupt vertices answer adversarially. The paper establishes a sharp threshold in the number of queries needed to identify the truthful set up to a small symmetric difference: if the truthful majority is small, specifically $|T|-|B|\\le n^{1/2-\\beta}$, then $\\Theta(n\\log n)$ queries are necessary and sufficient; if instead $|T|=(1/2+\\delta)n$ for a constant $\\delta>0$, then $O(n)$ queries suffice on graphs with strong expansion. These results answer an open question from the earlier work that introduced the model, and show that the difficulty of the problem is governed by the size of the truthful majority. A reader should care because the result pinpoints the amount of evidence needed to detect corruption under noisy queries.","feed_headline":"Thin truthful majority forces n log n queries in noisy graph tests","feed_subtitle":"A constant-majority graph needs only linear queries to identify the corrupt side.","key_machinery":"The lower bound uses the notion of an obscured vertex: a vertex whose every incident query is answered by a fair coin flip, so that it receives and sends only random noise. The key identity is Lemma 2.3, which states that for any fixed obscured set $O$ of size at least $n^{1-\\beta}$, a random partition with $0\\le |T|-|B|\\le n^{1/2-\\beta}$ satisfies $\\Pr[|T\\setminus O|\\ge |B\\setminus O|]\\le 1/2+o(1)$; this makes it impossible to determine which side of the remaining graph is truthful better than a coin flip. The upper bound is carried by the $\\delta$-excellent expander condition—any two disjoint vertex sets of size $\\delta n$ share an edge—which, after error amplification by repeated queries, guarantees that any two large candidate clusters with few cross-accusations must be close to the true truthful set. Both mechanisms together show that the query complexity is determined by whether the truthful majority is sub-polynomial or constant.","core_discovery":"The central claim is a phase transition in query complexity. On any constant-degree graph, if the truthful set exceeds the corrupt set by at most $n^{1/2-\\beta}$ for a fixed $\\beta>0$, any algorithm that uses $o(n\\log n)$ queries can find a set $T'$ with $|T\\triangle T'|\\le n/10$ with probability at most $1/2+o(1)$; alongside the matching $O(n\\log n)$-query algorithm, this makes the query complexity $\\Theta(n\\log n)$. On the other hand, on a constant-degree $\\delta$-excellent expander—a graph in which any two disjoint sets of size $\\delta n$ have an edge between them—the paper gives an algorithm using $O(n)$ queries that, with high probability, finds $T'$ and $B'$ with $|T\\triangle T'|,|B\\triangle B'|\\le 6\\delta n$ whenever $|T|=(1/2+\\delta)n$. The lower bound works by an adversary that makes every rarely queried vertex 'obscured' (all answers involving it are pure random noise); after deleting the obscured set, the remaining truthful majority is nearly a fair coin flip. The upper bound amplifies each edge query a constant number of times and then uses expansion to locate two large clusters with few mutual accusations.","pith_inferences":["If the conditional-dependence gap in the lower bound is real, an adaptive player might exploit the correlation between the obscured set and the true partition, potentially yielding a sublinear-query algorithm in the bare-majority regime; this is worth testing in simulation.","The sharp transition in query complexity mirrors a known gap between detection and recovery in planted-bisection problems: a tiny signal surplus hides the truth from any sublinear number of queries, while a constant surplus allows recovery at linear cost.","The exponential-time search in the robust-majority algorithm might be replaceable by a polynomial-time spectral or local-voting method, since the expansion assumption already guarantees that most neighborhoods have a clear truthful majority.","One could empirically probe the threshold by simulating the game on random regular graphs across a range of majority surpluses ($n^{1/4}$, $n^{1/3}$, $n^{1/2}$) and measuring the query count at which success probability departs from $1/2$; a smooth interpolation would suggest the lower-bound technique is not tight."],"forward_implications":["Any algorithm that uses $o(n\\log n)$ queries will fail with probability close to $1/2$ when the truthful majority is at most $n^{1/2-\\beta}$, so the straightforward scheme of querying each edge $O(\\log n)$ times and taking majorities is essentially optimal.","When the truthful majority is a constant fraction, $O(n)$ queries are enough, so the problem becomes feasible with a linear number of queries; the paper's own search procedure is not known to run in polynomial time.","The $\\Omega(n\\log n)$ lower bound applies to every constant-degree graph, making it a fundamental information-theoretic limit in the bare-majority regime, independent of expansion.","The $O(n)$ upper bound requires only the $\\delta$-excellent expansion property, which is weaker than spectral expansion but stronger than the $\\delta$-good expansion used in the noiseless setting; whether the assumption can be relaxed to $\\delta$-good expanders is left open.","The regime where the majority surplus lies between $n^{1/2-\\beta}$ and a constant fraction remains unresolved, with no tight bound known."],"supporting_citations":[{"why":"Defines the corruption detection model and the δ-good expander setting, proves the noiseless baseline results that the algorithm reduces to, and poses the noisy setting as an open question.","marker":"[1]"}],"fun_headline_variants":["Noisy graph test needs n log n queries unless expander","Phase transition: n log n queries for noisy graph majority","Answer to Alon-Mossel-Pemantle: noisy corruption needs n log n","Expander graphs cut noisy detection queries to linear"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound assumes that the set of obscured vertices—vertices whose every answer is pure random noise—can be treated as fixed before the truthful/corrupt partition is chosen, even though the player's queries, and hence this set, may depend on the partition through the answers received.","fun_headline_variants_meta":{"raw":{"variants":["Noisy graph test needs n log n queries unless expander","Phase transition: n log n queries for noisy graph majority","Answer to Alon-Mossel-Pemantle: noisy corruption needs n log n","Expander graphs cut noisy detection queries to linear"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000662,"raw_usage":{"total_tokens":2959,"prompt_tokens":813,"completion_tokens":2146,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":429,"completion_tokens_details":{"reasoning_tokens":2073}},"tokens_in":429,"tokens_out":2146,"duration_ms":15149,"temperature":1.0,"reasoning_tokens":2073,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:20:30.681559+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the lower-bound adversary on a constant-degree expander with $|T|-|B|=1$ and let the player use an adaptive strategy that spends $o(n\\log n)$ queries; if the player's success probability exceeds $1/2+o(1)$, the claimed $\\Omega(n\\log n)$ lower bound is false.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the corruption detection model and the δ-good expander setting, proves the noiseless baseline results that the algorithm reduces to, and poses the noisy setting as an open question."}],"review_version":1}