Coding-theoretic approaches for resilient, secure distributed computing and learning

"Join by Zoom or in person @ SEC 3.301+ 3.302. In person attendees should follow the current SEAS masking and testing policies."

This talk present ideas in "coded computing”, an emerging sub-area of coding theory that injects data redundancy with the goal of protecting the output of a distributed function computations from errors and failures. Coded computing techniques can mitigate straggler bottlenecks in distributed computing, enable secure computation over untrusted devices, and ensure data privacy by adapting and generalizing secret sharing techniques. 

We briefly survey coding techniques for certain ubiquitous linear algebraic operations starting the 1980s, and describe recent polynomial-evaluation-based solutions that yield significant improvements in the trade-off between fault-tolerance and redundancy.  We study the effect of finite precision on numerical stability of our codes, and present new code constructions based on Chebyshev-Vandermonde systems and condition number bounds. Our study leads to a surprising threshold phenomenon on the trade-off between approximation error, finite precision and fault-tolerance. Finally, we outline methods to apply the developed codes to a wide class of computations beyond linear computations, and describe some interesting open directions. Experimental results in the contexts of resilient distributed training and inference in machine learning will be presented to demonstrate the promise of the ideas in practice.