46 citations · 313 across the 68 of their papers we have counts for
7 papers · 1 filter
Self-Adjusting Networks to Minimize Expected Path Length
Chen Avin, Michael Borokhovich, Bernhard Haeupler +1
Given a network infrastructure (e.g., data-center or on-chip-network) and a distribution on the source-destination requests, the expected path (route) length is an important measur…
Computing a Maximal Independent Set Using Beeps
Alejandro Cornejo, Bernhard Haeupler, Fabian Kuhn
We consider the problem of finding a maximal independent set (MIS) in the discrete beeping model. At each time, a node in the network can either beep (i.e., emit a signal) or be si…
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew +2
We present two on-line algorithms for maintaining a topological order of a directed -vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first…
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner +1
In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. I…
Faster Information Dissemination in Dynamic Networks via Network Coding
Bernhard Haeupler, David Karger
We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively choos…
Optimality of Network Coding in Packet Networks
Bernhard Haeupler, MinJi Kim, Muriel Médard
We resolve the question of optimality for a well-studied packetized implementation of random linear network coding, called PNC. In PNC, in contrast to the classical memoryless sett…