Speaker: Jared Saia

Title: Computing with Unknown Noise

Host: Mahdi Zamani

Abstract:

How can we compute over a noisy channel? Say Alice and Bob want to run a distributed algorithm, but they can only communicate over a channel where some number of bits may be flipped. What is the smallest number of bits they must send in order to obtain the correct output, with high probability? This general problem is called Interactive Communication (IC).

Several results in IC take a protocol requiring L bits of noise-free communication and make it robust over a channel with adversarial noise. In a recent result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal. However, his algorithm critically requires a priori knowledge of the number of bits that will be flipped by the adversary.

In this talk, we describe an algorithm requiring no such knowledge. If an adversary flips T bits, our algorithm sends L + soft-O (T + √ (LT)) bits in expectation and succeeds with high probability in L. 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 such an assumption is necessary when the amount of noise is unknown.

Bio

Jared Saia obtained his PhD from the University of Washington, and is now a professor at the University of New Mexico. His broad research interests are in theory and algorithms with strong interests in distributed computing, cybersecurity, game theory, and spectral methods. A general interest is determining how large groups can function robustly. He is the recipient of the NSF CAREER Award, the UNM School of Engineering Junior and Senior Faculty Research Excellence Awards, and several best paper awards. In his free time, he enjoys good food, hiking, and playing American handball.