Matrix multiplication is, oftentimes, the most expensive computational task in an algorithm. It is the computational bottleneck for training many of the now well-celebrated learning algorithms, for example. To speed up the algorithm, the data can be distributed on many machines to perform the computations in parallel. This sharing of the data, however, raises security concerns when the data is sensitive and has to remain private, such as financial or medical data. Secure distributed matrix multiplication (SDMM) studies how to parallelize matrix multiplication while keeping the data secure.
In this talk, I will present a combinatorial tool, called the degree table, and show how to utilize it to construct codes for SDMM which are currently the best performing for their parameters. I will also show lower bounds for our technique and characterize the total time complexity for SDMM codes, showing that if the parameters of the code are not chosen carefully, the total time might be larger than simply performing the computation locally.
Rafael G. L. D’Oliveira is a postdoctoral research associate with the Research Laboratory of Electronics at the Massachusetts Institute of Technology. He received a B.S. and an M.S. degree in mathematics and a Ph.D. degree in applied mathematics from the University of Campinas, Brazil, in 2009, 2012, and 2017. He was a postdoctoral research associate with Rutgers University from 2018 to 2019 and with the Illinois Institute of Technology in 2017, and did a research internship at Telecom ParisTech from 2015 to 2016. His research interests include Privacy and Security, Distributed Computing, Coding Theory, and Information Theory.