  In distortion-based analysis of social choice rules over metric spaces, one
assumes that all voters and candidates are jointly embedded in a common metric
space. Voters rank candidates by non-decreasing distance. The mechanism,
receiving only this ordinal (comparison) information, should select a candidate
approximately minimizing the sum of distances from all voters. It is known that
while the Copeland rule and related rules guarantee distortion at most 5, many
other standard voting rules, such as Plurality, Veto, or $k$-approval, have
distortion growing unboundedly in the number $n$ of candidates.
  Plurality, Veto, or $k$-approval with small $k$ require less communication
from the voters than all deterministic social choice rules known to achieve
constant distortion. This motivates our study of the tradeoff between the
distortion and the amount of communication in deterministic social choice
rules.
  We show that any one-round deterministic voting mechanism in which each voter
communicates only the candidates she ranks in a given set of $k$ positions must
have distortion at least $\frac{2n-k}{k}$; we give a mechanism achieving an
upper bound of $O(n/k)$, which matches the lower bound up to a constant. For
more general communication-bounded voting mechanisms, in which each voter
communicates $b$ bits of information about her ranking, we show a slightly
weaker lower bound of $\Omega(n/b)$ on the distortion.
  For randomized mechanisms, it is known that Random Dictatorship achieves
expected distortion strictly smaller than 3, almost matching a lower bound of
$3-\frac{2}{n}$ for any randomized mechanism that only receives each voter's
top choice. We close this gap, by giving a simple randomized social choice rule
which only uses each voter's first choice, and achieves expected distortion
$3-\frac{2}{n}$.
