  This paper proves strong lower bounds for distributed computing in the
CONGEST model, by presenting the bit-gadget: a new technique for constructing
graphs with small cuts.
  The contribution of bit-gadgets is twofold. First, developing careful sparse
graph constructions with small cuts extends known techniques to show a
near-linear lower bound for computing the diameter, a result previously known
only for dense graphs. Moreover, the sparseness of the construction plays a
crucial role in applying it to approximations of various distance computation
problems, drastically improving over what can be obtained when using dense
graphs.
  Second, small cuts are essential for proving super-linear lower bounds, none
of which were known prior to this work. In fact, they allow us to show
near-quadratic lower bounds for several problems, such as exact minimum vertex
cover or maximum independent set, as well as for coloring a graph with its
chromatic number. Such strong lower bounds are not limited to NP-hard problems,
as given by two simple graph problems in P which are shown to require a
quadratic and near-quadratic number of rounds. All of the above are optimal up
to logarithmic factors. In addition, in this context, the complexity of the
all-pairs-shortest-paths problem is discussed.
  Finally, it is shown that graph constructions for CONGEST lower bounds
translate to lower bounds for the semi-streaming model, despite being very
different in its nature.
