Tessellated distributed computing of non-linearly separable functions

The work considers the -server distributed computing scenario with  users requesting functions that are arbitrary multi-variable polynomial evaluations of  real (potentially non-linear) basis subfunctions of a certain degree. Our aim is to reduce both the computational cost at the servers, as well as the load of communication between the servers and the users. To do so, we take a novel approach, which involves transforming our distributed computing problem into a sparse tensor factorization problem , where tensor  represents the requested non-linearly-decomposable jobs expressed as the mode-1 product between tensor  and matrix , where  and  respectively define the communication and computational assignment, and where their sparsity respectively allows for reduced communication and computational costs.

We here design an achievable scheme, designing  by utilizing novel fixed-support SVD-based tensor factorization methods that first split  into properly sized and carefully positioned subtensors, and then decompose them into properly designed subtensors of  and submatrices of . For the zero-error case and under basic dimensionality assumptions, this work reveals a lower bound on the optimal rate  with a given communication and computational load.