On the Local Communication Complexity of Counting and Modular Arithmetic
share
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.
READ FULL TEXT