10 citations · 27 across the 16 of their papers we have counts for
5 papers · 1 filter
On the Local Communication Complexity of Counting and Modular Arithmetic
Bala Kalyanasundaram, Calvin Newport
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…
Distributed Algorithms for Minimum Degree Spanning Trees
Michael Dinitz, Magnús M. Halldórsson, Calvin Newport
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree for graph with vertices, such that the maximum degree of is t…
Gossip in a Smartphone Peer-to-Peer Network
Calvin Newport
In this paper, we study the fundamental problem of gossip in the mobile telephone model: a recently introduced variation of the classical telephone model modified to better describ…
How to Discreetly Spread a Rumor in a Crowd
Mohsen Ghaffari, Calvin Newport
In this paper, we study PUSH-PULL style rumor spreading algorithms in the mobile telephone model, a variant of the classical telephone model in which each node can participate in a…
Bounds on Contention Management in Radio Networks
Mohsen Ghaffari, Bernhard Haeupler, Nancy Lynch +1
The local broadcast problem assumes that processes in a wireless network are provided messages, one by one, that must be delivered to their neighbors. In this paper, we prove tight…