Expansion-corruption detection gap in networks

Open Problem: Expansion vs. Corruption Detection · arXiv:1505.05637

arXiv Informal medium confidence— first stated 2020-03-12

Authors: Noga Alon, Elchanan Mossel, Robin Pemantle

Status open high confidence

The open problem asks for a tight characterization of which graph expansion properties are necessary and sufficient for corruption detection, closing the gap between the Ramanujan-type spectral sufficiency (Theorem 1.4, requiring \lambda \leq 2\sqrt{d-1}) and the vertex-separator impossibility (Proposition 1.6). Two directly related papers appeared before the 2020 journal publication: Jin, Mossel, and Ramnarayan (arXiv:1809.10325, ITCS 2019) characterize corruption detection on arbitrary graphs via a vertex separability parameter but do not close the spectral expansion gap; Alweiss (arXiv:1908.07493, 2019) addresses a noisy variant of the model. No post-2020 paper resolving the specific expansion gap was found in a broad web search.

Reviewer notes. Two pre-2020 follow-up papers address related but distinct questions: arXiv:1809.10325 (Jin, Mossel, Ramnarayan, 2018; ITCS 2019) characterizes detectable corruption on general graphs via a vertex-separability parameter m(G) and proves that finding an optimal corruption strategy is NP-hard under the Small Set Expansion Hypothesis; arXiv:1908.07493 (Alweiss, 2019) extends the model to a noisy setting and claims to answer a question of the original authors, but in the noisy (not expansion-gap) sense. Neither directly closes the gap between Ramanujan-type spectral conditions (sufficient) and vertex-separator conditions (necessary for impossibility). No post-2020 literature resolving this specific open problem was found.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. There is still a significant gap between the expansion properties that suffice for solving the detection problem (Theorem 1.4) and the conditions in Proposition 1.6 that are necessary for such a solution. It will be interesting to obtain tighter relations between expansion and corruption detection.

Context

Theorem 1.4 shows that strong spectral expansion (Ramanujan-type $(n,d,\lambda)$-graphs with $\lambda \leq 2\sqrt{d-1}$) suffices for identifying most truthful and corrupt vertices. Proposition 1.6 shows that if removing at most $\epsilon n$ vertices splits the graph into components of size at most $\epsilon n$, then no corruption detection is possible. The gap between these two regimes is noted by the authors as an open research direction.

Notes. No labelled theorem environment; stated as a research direction at the end of Section 1.1. Section 4, where this is said to be 'further discussed', is not present in the extracted text (PDF extraction appears truncated).

Source paper

Distributed Corruption Detection in Networks
Noga Alon, Elchanan Mossel, Robin Pemantle · 2020-03-12
https://arxiv.org/abs/1505.05637 PDF source