13 citations · 27 across the 11 of their papers we have counts for
3 papers · 1 filter
Algorithmic Polarization for Hidden Markov Models
Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan
Using a mild variant of polar codes we design linear compression schemes compressing Hidden Markov sources (where the source is a Markov chain, but whose state is not necessarily o…
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Mitali Bafna, Badih Ghazi, Noah Golowich +1
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively ge…
Synchronization Strings: List Decoding for Insertions and Deletions
Bernhard Haeupler, Amirbehshad Shahrasbi, Madhu Sudan
We study codes that are list-decodable under insertions and deletions. Specifically, we consider the setting where a codeword over some finite alphabet of size may suffer from…