Noisy Corruption Detection

Ryan Alweiss

REVIEW 2 major objections 3 minor 1 references

Noisy Corruption Detection

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read In noisy graph corruption detection, a slender truthful majority costs n log n queries, while a constant majority costs linear queries.

desk verdict 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. read the letter →

arxiv 1908.07493 v2 pith:N6JAVBDB submitted 2019-08-20 math.CO cs.DM

Ryan Alweiss This is my paper · ORCID

classification math.COcs.DM MSC 05C8568Q2568W20

keywords corruptiondetectionquerycomplexityexpandergraphsnoisyqueriesthresholdphenomenonlowerboundsgraphalgorithms

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

The 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.

The 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.

What'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.

For 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.

Referee Report

2 major / 3 minor

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.

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 (2)

[Section 2, proof of Theorem 2.2] 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 3, proof of Theorem 3.1] 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.

minor comments (3)

[Abstract and Introduction] The abstract contains a formatting artifact: 'corru ption' appears with an unwanted space. Please fix.
[Lemma 2.3] 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 4, Discussion] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's bounds reduce to the external AMP noiseless theorem and to self-contained probabilistic estimates; no fitted parameter is presented as a prediction.

full rationale

The paper does not exhibit any step in which a claimed output is equivalent by construction to an input. The lower bound (Theorem 2.2) constructs an adversarial coin-flip coupling, defines an obscured set O, and invokes Lemma 2.3; Lemma 2.3 is proved directly from a binomial/local-CLT estimate for a uniformly random partition, not by assuming the theorem's success bound. The upper bound (Theorem 3.1) amplifies accuracy by repeated queries and then uses the delta-excellent expansion property to certify that the recovered pair (X,Y) has small symmetric difference; no parameter is fitted to the data being 'predicted.' The only external input is the noiseless expander theorem of Alon-Mossel-Pemantle [1], which is a genuine reduction to a known result rather than a self-citation. The draft's acknowledged conditional-probability issue, namely that the event that v is obscured depends on a stopping time and can be correlated with T, is a possible gap in the proof of Theorem 2.2, but it is a probabilistic correctness concern, not a circularity: the proof does not define O in terms of the target sets T' and B', nor does it assume the conclusion. There is no self-citation chain, no imported uniqueness theorem, and no renaming of a known result. Score 0.

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

No numbers are fitted to data; all constants (c, δ, β, ε) are universal and can be chosen explicitly, so there are no free parameters in the empirical sense. The proof rests on standard probabilistic tools, the noiseless AMP theorem, the noisy Bernoulli model, and the δ-excellent expansion assumption. No new entities are postulated.

assumptions (4)

standard math Chernoff bounds and the local central limit theorem
Used in Lemma 2.3 and in the amplification arguments to convert per-query error probabilities into high-probability bounds.
domain assumption Alon-Mossel-Pemantle noiseless Theorem 1.1
Used in Theorem 2.1 to reduce the noisy O(n log n) upper bound to the deterministic setting. It is prior work, treated as external.
domain assumption δ-excellent expansion property, meaning any two disjoint δn-subsets have an edge
Assumed in Theorem 3.1; stronger than AMP's δ-good expansion, and the proof needs the derived 'all but δn vertices have a neighbor' consequence.
domain assumption Each truthful answer is independently correct with probability 1−ε
The noisy model defined in the introduction; the central results are stated relative to it.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Noisy Corruption Detection." pith.science (2026). https://pith.science/paper/N6JAVBDB

@misc{pith2026190807493,
  author       = {Pith},
  title        = {Pith review of: Noisy Corruption Detection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N6JAVBDB}},
  note         = {Machine review of arXiv:1908.07493}
}

read the original abstract

We answer a question of Alon, Mossel, and Pemantle about the corruption detection model on graphs in the noisy setting.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

1 extracted references · 1 canonical work pages

[1]

[1] N. Alon, E. Mossel, and R. Pemantle, Corruption Detectio n on Networks, preprint, 2015 (to appear in Theory of Computing). 7

work page 2015

Pith tools

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

[1] [1]

[1] N. Alon, E. Mossel, and R. Pemantle, Corruption Detectio n on Networks, preprint, 2015 (to appear in Theory of Computing). 7

work page 2015