2015/04/23 by Varsha Dani, Thomas P. Hayes, Dani, Varsha +7 · 1 citation
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS #cs.IT #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.1504.06316
Made substantial improvements to the algorithm and analysis. Previous version had a subtle error involving the adversary's ability to attack fingerprints
arxiv created 2015/08/13 · arxiv updated 2015/08/17
Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring L bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires a priori knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips T bits, our algorithm sends L + O(√(L(T+1)log L) + T) bits in expectation and succeeds with high probability in L. It does so without any a priori knowledge of T. Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.