Vinayak Ramkumar
Postdoctoral Fellow, Tel Aviv University 
Visiting Researcher, Washington University in St. Louis

Given a dataset to store in a distributed system and a family of computations (e.g., polynomials, neural networks, classifiers, etc.), we wish to store the dataset in a distributed manner so that any computation from this family can be performed by accessing a small number of servers, called the access parameter of the system. Doing so relieves the remaining servers to execute other tasks, and can reduce the overall communication in the system. Optimizing such system design gives rise to an access-redundancy tradeoff, where a smaller access parameter requires more redundancy in the system and vice versa.   

In this talk, I'll discuss such access-redundancy tradeoffs, with a focus on quantized linear computations. Linear real-valued computations over distributed datasets are common in many applications, most notably as part of machine learning inference. In particular, linear computations that are quantized, i.e., where the coefficients are restricted to a predetermined set of values (such as +/- 1), have gained increasing interest lately due to their role in efficient, robust, or private machine learning models.  

Low-access schemes for linear computations have connections to the theory of covering codes, an information-theoretic notion which studies covering finite spaces by a few Hamming balls, and will be introduced in the talk. Based on this theory, low-access schemes for +/-1 computations will be presented, which improve upon existing works dating back to the early 2000's. I will also briefly discuss a new additive-combinatorics notion we call coefficient complexity, which turned out to be helpful in extending our schemes to all possible quantizations.

This talk is based on joint work with Netanel Raviv and Itzhak Tamo.