  We study the communication cost (or message complexity) of fundamental
distributed symmetry breaking problems, namely, coloring and MIS. While
significant progress has been made in understanding and improving the running
time of such problems, much less is known about the message complexity of these
problems. In fact, all known algorithms need at least $\Omega(m)$ communication
for these problems, where $m$ is the number of edges in the graph. We address
the following question in this paper: can we solve problems such as coloring
and MIS using sublinear, i.e., $o(m)$ communication, and if so under what
conditions? [See full abstract in pdf]
