It was ``all'' for ``nothing'': sharp phase transitions for noiseless discrete channels

Ilias Zadik , Jonathan Niles-Weed

[Proceedings link] [PDF]

Session: Regression and High-Dimensional Statistics (B)

Session Chair: Yuting Wei

Poster: Poster Session 3

Abstract: We prove a phase transition known as the ``all-or-nothing'' phenomenon for noiseless discrete channels. This class of models includes the Bernoulli group testing model and the planted Gaussian perceptron model. Previously, the existence of the all-or-nothing phenomenon for such models was only known in a limited range of parameters. Our work extends the results to all signals with sublinear sparsity. Our main technique is to show that for such models, the ``all'' half of all-or-nothing implies the ``nothing'' half, so that a proof of ``all'' can be turned into a proof of ``nothing.'' Since the ``all'' half can often be proven by straightforward means, our equivalence gives a powerful and general approach towards establishing the existence of this phenomenon in other contexts.

Summary presentation

Full presentation