10 citations · 27 across the 16 of their papers we have counts for
21 papers
Smoothed Analysis of Information Spreading in Dynamic Networks
Michael Dinitz, Jeremy Fineman, Seth Gilbert +1
The best known solutions for -message broadcast in dynamic networks of size require rounds. In this paper, we see if these bounds can be improved by smoothed analysi…
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…
Contention Resolution with Predictions
Seth Gilbert, Calvin Newport, Nitin Vaidya +1
In this paper, we consider contention resolution algorithms that are augmented with predictions about the network. We begin by studying the natural setup in which the algorithm is…
Asynchronous Gossip in Smartphone Peer-to-Peer Networks
Calvin Newport, Alex Weaver, Chaodong Zheng
In this paper, we study gossip algorithms in communication models that describe the peer-to-peer networking functionality included in most standard smartphone operating systems. We…
The Capacity of Smartphone Peer-to-Peer Networks
Michael Dinitz, Magnús M. Halldórsson, Calvin Newport +1
We study three capacity problems in the mobile telephone model, a network abstraction that models the peer-to-peer communication capabilities implemented in most commodity smartpho…
Random Gossip Processes in Smartphone Peer-to-Peer Networks
Calvin Newport, Alex Weaver
In this paper, we study random gossip processes in communication models that describe the peer-to-peer networking functionality included in standard smartphone operating systems. R…
Approximate Neighbor Counting in Radio Networks
Calvin Newport, Chaodong Zheng
For many distributed algorithms, neighborhood size is an important parameter. In radio networks, however, obtaining this information can be difficult due to ad hoc deployments and…
Fault-Tolerant Consensus with an Abstract MAC Layer
Calvin Newport, Peter Robinson
In this paper, we study fault-tolerant distributed consensus in wireless systems. In more detail, we produce two new randomized algorithms that solve this problem in the abstract M…
On Bioelectric Algorithms: A Novel Application of Theoretical Computer Science to Core Problems in Developmental Biology
Seth Gilbert, James Maguire, Calvin Newport
Cellular bioelectricity describes the biological phenomenon in which cells in living tissue generate and maintain patterns of voltage gradients induced by differing concentrations…
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…
On Simple Back-Off in Unreliable Radio Networks
Seth Gilbert, Nancy Lynch, Calvin Newport +1
In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work…
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…
The Computational Power of Beeps
Seth Gilbert, Calvin Newport
In this paper, we study the quantity of computational resources (state machine states and/or probabilistic transition precision) needed to solve specific problems in a single hop n…
Smoothed Analysis of Dynamic Networks
Michael Dinitz, Jeremy T. Fineman, Seth Gilbert +1
We generalize the technique of smoothed analysis to distributed algorithms in dynamic network models. Whereas standard smoothed analysis studies the impact of small random perturba…
Lower Bounds for Structuring Unreliable Radio Networks
Calvin Newport
In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio netw…
Radio Network Lower Bounds Made Easy
Calvin Newport
Theoreticians have studied distributed algorithms in the radio network model for close to three decades. A significant fraction of this work focuses on lower bounds for basic commu…
Trade-offs between Selection Complexity and Performance when Searching the Plane without Communication
Christoph Lenzen, Nancy Lynch, Calvin Newport +1
We consider the ANTS problem [Feinerman et al.] in which a group of agents collaboratively search for a target in a two-dimensional plane. Because this problem is inspired by the b…
Multi-Message Broadcast with Abstract MAC Layers and Unreliable Links
Mohsen Ghaffari, Erez Kantor, Nancy Lynch +1
We study the multi-message broadcast problem using abstract MAC layer models of wireless networks. These models capture the key guarantees of existing MAC layers while abstracting…
Consensus with an Abstract MAC Layer
Calvin Newport
In this paper, we study distributed consensus in the radio network setting. We produce new upper and lower bounds for this problem in an abstract MAC layer model that captures the…
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…