  In standard number-in-hand multi-party communication complexity, performance
is measured as the total number of bits transmitted globally in the network. In
this paper, we study a variation called local communication complexity in which
performance instead measures the maximum number of bits sent or received at any
one player. We focus on a simple model where $n$ players, each with one input
bit, execute a protocol by exchanging messages to compute a function on the $n$
input bits. We ask what can and cannot be solved with a small local
communication complexity in this setting. We begin by establishing a
non-trivial lower bound on the local complexity for a specific function by
proving that counting the number of $1$'s among the first $17$ input bits
distributed among the participants requires a local complexity strictly greater
than $1$. We further investigate whether harder counting problems of this type
can yield stronger lower bounds, providing a largely negative answer by showing
that constant local complexity is sufficient to count the number $1$ bits over
the entire input, and therefore compute any symmetric function. In addition to
counting, we show that both sorting and searching can be computed in constant
local complexity. We then use the counting solution as a subroutine to
demonstrate that constant local complexity is also sufficient to compute many
standard modular arithmetic operations on two operands, including: comparisons,
addition, subtraction, multiplication, division, and exponentiation. Finally we
establish that function $GCD(x,y)$ where $x$ and $y$ are in the range $[1,n]$
has local complexity of $O(1)$. Our work highlights both new techniques for
proving lower bounds on this metric and the power of even a small amount of
local communication.
