47 citations · 207 across the 54 of their papers we have counts for
6 papers · 1 filter
Optimal Error Rates for Interactive Coding I: Adaptivity and Other Settings
Mohsen Ghaffari, Bernhard Haeupler, Madhu Sudan
We consider the task of interactive communication in the presence of adversarial errors and present tight bounds on the tolerable error-rates in a number of different settings. Mos…
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
Mohsen Ghaffari, Bernhard Haeupler
We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any -round interactive protocol using rounds over an adv…
Distributed Connectivity Decomposition
Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
We present time-efficient distributed algorithms for decomposing graphs with large edge or vertex connectivity into multiple spanning or dominating trees, respectively. As their pr…
Distributed Minimum Cut Approximation
Mohsen Ghaffari, Fabian Kuhn
We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round, bits…
A New Perspective on Vertex Connectivity
Keren Censor-Hillel, Mohsen Ghaffari, Fabian Kuhn
Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge…
A Bound on the Throughput of Radio Networks
Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian
We consider the well-studied radio network model: a synchronous model with a graph G=(V,E) with |V|=n where in each round, each node either transmits a packet, with length B=Omega(…