It Was “all” for “nothing”: Sharp Phase Transitions for Noiseless Discrete Channels

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.