Title: Low-bandwidth Recovery of Linear Functions of Reed-Solomon-encoded Data
Speaker: Mary Wootters
Date and Time: 10/07/2021 4:10PM ET
Location: Phillips 233 and Zoom
Abstract: We study the problem of efficiently computing on encoded data. More specifically, we study the question of communication-efficient computation of a function f(x), given access to an encoding c = Enc(x) under an error correcting code. In our model—relevant in distributed storage, distributed computation and secret sharing—each symbol of c is held by a different party, and we aim to minimize the total amount of information downloaded from each party to compute f(x). Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute any linear function on Reed-Solomon-encoded data, even in the presence of erasures. This has applications in distributed storage, coded computation, and homomorphic secret sharing. This is joint work with Noah Shutty.
Bio: Mary Wootters is an assistant professor of Computer Science and Electrical Engineering at Stanford University. She received a PhD in mathematics from the University of Michigan in 2014, and a BA in math and computer science from Swarthmore College in 2008; she was an NSF postdoctoral fellow at Carnegie Mellon University from 2014 to 2016. She works in theoretical computer science, applied math, and information theory; her research interests include error correcting codes and randomized algorithms for dealing with high dimensional data. She is the recipient of an NSF CAREER award and was named a Sloan Research Fellow in 2019; she was named to the Stanford Tau Beta Pi Teaching honor roll in 2018-19, 19-20, and 20-21.