  We establish 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
arbitrary sublinear sparsity.
  Over the past several years, the all-or-nothing phenomenon has been
established in various models as an outcome of two seemingly disjoint results:
one positive result establishing the "all" half of all-or-nothing, and one
impossibility result establishing the "nothing" half. Our main technique in the
present work is to show that for noiseless discrete channels, the "all" half
implies the "nothing" half, that is a proof of "all" can be turned into a proof
of "nothing." Since the "all" half can often be proven by straightforward means
-- for instance, by the first-moment method -- our equivalence gives a powerful
and general approach towards establishing the existence of this phenomenon in
other contexts.
