The work considers the N-server distributed computing scenario with K users requesting functions that are linearly-decomposable over an arbitrary basis of L real (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion) ϵ, reduced computing cost (γ; the fraction of subfunctions each server must compute), and reduced communication cost (δ; the fraction of users each server must connect to). For any given set of K requested functions-which is here represented by a coefficient matrix F ∈ R K×L-our problem is made equivalent to the open problem of sparse matrix factorization that seeks-for a given parameter T , representing the number of shots for each server-to minimize the reconstruction distortion 1 KL ∥F − DE∥ 2 F over all δ-sparse and γ-sparse matrices D ∈ R K×N T and E ∈ R N T ×L. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our D, E by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split F into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of D and E. For the zero-error case and under basic dimensionality assumptions, the work reveals achievable computationvs-communication corner points (γ, δ) which, for various cases, are proven optimal over a large class of D, E by means of a novel tessellations-based converse. Subsequently, for large N , and under basic statistical assumptions on F, the average achievable error ϵ is concisely expressed using the incomplete first moment of the standard Marchenko-Pastur distribution, where this performance is shown to be optimal over a large class of D and E. In the end, the work also reveals that the overall achieved gains over baseline methods are unbounded.

In this work, we explore the problem of multi-user linearly-separable distributed computation, where N servers help compute the desired functions (jobs) of K users, and where each desired function can be written as a linear combination of up to L (generally non-linear) subtasks (or sub-functions). Each server computes some of the subtasks, communicates a function of its computed outputs to some of the users, and then each user collects its received data to recover its desired function. We explore the computation and communication relationship between how many servers compute each subtask vs. how much data each user receives. For a matrix F representing the linearly-separable form of the set of requested functions, our problem becomes equivalent to the open problem of sparse matrix factorization F=DE over finite fields, where a sparse decoding matrix D and encoding matrix E imply reduced communication and computation costs respectively. This paper establishes a novel relationship between our distributed computing problem, matrix factorization, syndrome decoding and covering codes. To reduce the computation cost, the above D is drawn from covering codes or from a here-introduced class of so-called ‘partial covering’ codes, whose study here yields computation cost results that we present.