13 citations · 27 across the 11 of their papers we have counts for
4 papers · 1 filter
A Self-contained Analysis of the Lempel-Ziv Compression Algorithm
Madhu Sudan, David Xiang
This article gives a self-contained analysis of the performance of the Lempel-Ziv compression algorithm on (hidden) Markovian sources. Specifically we include a full proof of the a…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Round Complexity of Common Randomness Generation: The Amortized Setting
Noah Golowich, Madhu Sudan
We study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples and , res…
Communication for Generating Correlation: A Unifying Survey
Madhu Sudan, Himanshu Tyagi, Shun Watanabe
The task of manipulating correlated random variables in a distributed setting has received attention in the fields of both Information Theory and Computer Science. Often shared cor…