Michael Langberg

SODA Conference 2017 Conference Paper

Tight Network Topology Dependent Bounds on Rounds of Communication

• Arkadev Chattopadhyay
• Michael Langberg
• Shi Li 0001
• Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied k -party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent such results on total communication that have received some attention. We also present some applications to distributed graph computation problems. Our main contribution is a proof technique that allows us to reduce the problem on a general graph topology to a relevant two-party communication complexity problem. However, unlike many previous works that also used the same high level strategy, we do not reason about a two-party communication problem that is induced by a cut in the graph. To ‘stitch’ back the various lower bounds from the two party communication problems, we use the notion of timed graph that has seen prior use in network coding. Our reductions use some tools from Steiner tree packing and multi-commodity flow problems that have a delay constraint.

STOC Conference 2015 Conference Paper

A Characterization of the Capacity of Online (causal) Binary Channels

• Zitan Chen
• Sidharth Jaggi
• Michael Langberg

In the binary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x 1 ,...,x n ) ∈ {0,1} n bit by bit via a channel limited to at most pn corruptions. The channel is "online" in the sense that at the ith step of communication the channel decides whether to corrupt the ith bit or not based on its view so far, i.e., its decision depends only on the transmitted bits (x 1 ,...,x i ). This is in contrast to the classical adversarial channel in which the error is chosen by a channel that has full knowledge of the transmitted codeword x. In this work we study the capacity of binary online channels for two corruption models: the bit-flip model in which the channel may flip at most pn of the bits of the transmitted codeword, and the erasure model in which the channel may erase at most pn bits of the transmitted codeword. Specifically, for both error models we give a full characterization of the capacity as a function of p. The online channel (in both the bit-flip and erasure case) has seen a number of recent studies which present both upper and lower bounds on its capacity. In this work, we present and analyze a coding scheme that improves on the previously suggested lower bounds and matches the previously suggested upper bounds thus implying a tight characterization.

STOC Conference 2011 Conference Paper

A unified framework for approximating and clustering data

• Dan Feldman
• Michael Langberg

SODA Conference 2010 Conference Paper

Universal epsilon-approximators for Integrals

• Michael Langberg
• Leonard J. Schulman

STOC Conference 2009 Conference Paper

Fault-tolerant spanners for general graphs

• Shiri Chechik
• Michael Langberg
• David Peleg
• Liam Roditty

TCS Journal 2007 Journal Article

The multi-multiway cut problem

• Adi Avidor
• Michael Langberg

In this paper, we define and study a natural generalization of the multicut and multiway cut problems: the minimum multi-multiway cut problem. The input to the problem is a weighted undirected graph G = ( V, E ) and k sets S 1, S 2, …, S k of vertices. The goal is to find a subset of edges of minimum total weight whose removal completely disconnects each one of the sets S 1, S 2, …, S k, i. e. , disconnects every pair of vertices u and v such that u, v ∈ S i, for some i. This problem generalizes both the multicut problem, when | S i | = 2, for 1 ≤ i ≤ k, and the multiway cut problem, when k = 1. We present an approximation algorithm for the multi-multiway cut problem with an approximation ratio which matches that obtained by Garg, Vazirani, and Yannakakis on the standard multicut problem. Namely, our algorithm has an O ( log k ) approximation ratio. Moreover, we consider instances of the minimum multi-multiway cut problem which are known to have an optimal solution of light weight. We show that our algorithm has an approximation ratio substantially better than O ( log k ) when restricted to such “light” instances. Specifically, we obtain an O ( log LP ) -approximation algorithm for the problem when all edge weights are at least 1 (here LP denotes the value of a natural linear programming relaxation of the problem). The latter improves the O ( log LP log log LP ) approximation ratio for the minimum multicut problem (implied by the work of Seymour and Even et al.).

SODA Conference 2006 Conference Paper

Analysis of incomplete data and an intrinsic-dimension Helly theorem

• Jie Gao 0001
• Michael Langberg
• Leonard J. Schulman

FOCS Conference 2004 Conference Paper

Private Codes or Succinct Random Codes That Are (Almost) Perfect

• Michael Langberg

Coding theory addresses the design and analysis of codes that enable communication over noisy channels. Two types of channels that have been extensively considered are the binary symmetric channel and the adversarial channel. In a binary symmetric channel each bit of the sent message is flipped independently with some probability p, implying that the noise imposed by the channel is random in nature where the amount of noise is determined by p. In an adversarial channel the message is treated as a whole, and the noise may be an arbitrary (and malicious) function of the message being sent, as long as it does not effect more that a certain fraction (say p) of the bits transmitted. Roughly speaking, any code designed for an adversarial channel can be used on a corresponding binary symmetric channel successfully, whereas the contrary is not necessarily true. In this work we present a construction that transforms the best codes for binary symmetric channels into "codes" for corresponding adversarial channels. The "codes" we present assume that the sender and the receiver of the message have a joint secret random string (which is not known to the channel). These codes are referred to as private codes. Intuitively, this private randomness allows a reduction between the random and adversarial channels. Such a reduction is simple once the size of the joint random string is /spl Theta/(n log n) (here the codes are a subset of {0, 1 }/sup n/). In this work we present private codes in which the size of the joint random string is O(log n). Moreover, we show that our result is tight. Namely, to design private codes that allow communication over adversarial channels that meet the bounds achievable when communicating over binary symmetric channels, an amount of /spl Omega/(log n) shared random bits are required. To the best of our knowledge, no prior results of this nature have been presented in the past. As part of our proof we establish a connection between list decodable codes and private codes which complements a recent result of Guruswami (CCC '03) on list decoding with side information.

FOCS Conference 2002 Conference Paper

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers

• Uriel Feige
• Michael Langberg
• Gideon Schechtman

Karger Motwani and Sudan (1998) introduced the notion of a vector coloring of a graph. In particular they show that every k-colorable graph is also vector k-colorable, and that for constant k, graphs that are vector k-colorable can be colored by roughly /spl Delta//sup 1-2/k/ colors. Here /spl Delta/ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set. We show that for every positive integer k there are graphs that are vector k-colorable but do not have independent sets significantly larger than n//spl Delta//sup 1-2/k/ (and hence cannot be colored with significantly less that /spl Delta//sup 1-2/k/ colors). For k = O(log n/log log n) we show vector k-colorable graphs that do not have independent sets of size (log n)/sup c/, for some constant c. This shows that the vector chromatic number does not approximate the chromatic number within factors better than n/polylogn. As part of our proof, we analyze "property testing" algorithms that distinguish between graphs that have an independent set of size n/k, and graphs that are "far" from having such an independent set. Our bounds on the sample size improve previous bounds of Goldreich, Goldwasser and Ron (1998) for this problem.