Monotone interference growth with network depth

Open Problem (interference worsens with depth) · arXiv:1611.02400

arXiv Informal medium confidence— first stated 2017-06-09

Authors: Noga Alon, Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Ozcimder, Daniel Reichman, Igor Shinkar, Tal Wagner

Status open medium confidence

The conjecture that interference in d-regular networks worsens monotonically as depth r increases beyond 2 remains open. Follow-up papers on multitasking capacity (arXiv:1809.02835) and topological limits to parallel processing (arXiv:1708.03263, published in Nature Physics 2021) address related combinatorial and statistical-mechanics questions but do not resolve the depth-monotonicity question. No paper settling this specific open problem was found in the literature.

Reviewer notes. Two directly related follow-up papers were found and checked: arXiv:1809.02835 (Alon et al., 2018) on hardness results and improved constructions for multitasking capacity, and arXiv:1708.03263 / Nature Physics 17 (2021) on topological limits. Neither addresses the depth-monotonicity conjecture. The conjecture is ~9 years old, so medium confidence is appropriate — absence of follow-up may reflect the narrowness of the specific open problem rather than an easy resolution.

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

Informal. We believe that it is also the case that interference gets worst with $r$ (namely that interference worsens as $r$ increases to $r+1$ for $r > 2$), although whether this is indeed the case is an open problem.

Context

The paper proves that for $d$-regular networks of depth $r$ the multitasking capacity for task sets of size $n$ is at most $O\!\left(\frac{r}{d^{1-1/r}}\right)$, showing depth-$r$ networks suffer strictly more interference than depth-2 networks when $2 < r \ll d$. The authors then conjecture that interference continues to worsen monotonically as depth increases beyond 2.

Notes. Statement appears in running prose without a labelled environment; PDF source.

Source paper

A Graph-Theoretic Approach to Multitasking
Noga Alon, Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Ozcimder, Daniel Reichman, Igor Shinkar, Tal Wagner · 2017-06-09
https://arxiv.org/abs/1611.02400 PDF source