Coding Theory for Distributed Computation

Thursday, October 1, 2020 - 2:00pm to Friday, October 2, 2020 - 2:55pm

Event Calendar Category

Other LIDS Events

Speaker Name

Qian Yu

Affiliation

University of Southern California (USC)

Zoom meeting id

991 1926 6347

Join Zoom meeting

https://mit.zoom.us/s/99119266347

Join by Skype for Business

https://mit.zoom.us/skype/99119266347

Abstract

This talk will cover coding-theoretic and converse-bounding techniques developed recently in the area of coded computing. In the first part, we focus on a standard setup where the computation is carried out using a set of worker nodes, and an unknown subset could fail to return their computing results (referred to as stragglers). The goal is to find functions to encode the input data to tolerate as many stragglers as possible. Compared to classical coding theory, new classes of constructions are needed to optimally match the algebraic process of the computation. We illustrate some main techniques using block matrix multiplication as an example. In the second part of this talk, we consider the problem of coding for communication reduction. We present an information-theoretic lower bound on the communication rates for delivering messages in general networks. The presented bound strictly improves the compound cut-set, and exactly matches the inverse-proportion law achieved by coded multicast.

Biography

Qian Yu has received a Ph.D. degree in Electrical and Computer Engineering at University of Southern California (USC), Viterbi School of Engineering. He received an M.Eng. degree in Electrical Engineering and a B.S. degree in EECS and Physics, both from Massachusetts Institute of Technology (MIT). His interests span information theory, distributed computing, and many other problems math-related. Qian is a recipient of the Google PhD Fellowship in 2018, and received the Jack Keil Wolf ISIT Student Paper Award in 2017.