Computing with Unknown Noise

Departments: Computer Science
Time: Thursday, October 13, 2016 - 4:00pm - 5:00pm
Type: Seminar Series
Presenter: Jared Saia, University of New Mexico
Room/Office: AKW 200
Location:
51 Prospect Street
New Haven, CT 06511
United States
See map: Google Maps

Computer Science Colloquium

Title: Computing with Unknown Noise

Presenter: Jared Saia, University of New Mexico

Host: Mahdi Zamani/Joan Feigenbaum

Event time: Thursday, October 13, 2016 at 4:00pm

Location: AKW 200

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.