Multiple-Function Approximated Coded Computing: Constructions and Error Bounds
Abstract
Coded computing mitigates stragglers in distributed computation. While Lagrange coded computing (LCC) enables exact polynomial computation over finite fields, Berrut approximated coded computing (BACC) enables approximate computation of arbitrary, including non-polynomial, functions in the analog domain. In applications such as multi-task learning and inference, multiple functions must be evaluated over different subsets of a common dataset, making single-round computation desirable to reduce communication overhead. An existing LCC approach addresses this requirement but is restricted to polynomial functions over finite fields, leaving single-round multi-function computation in the analog domain an open problem. In this work, we develop a single-round construction for computing multiple arbitrary functions using BACC. We first extend the existing multi-function computation approach in LCC to the BACC setting and derive an approximation-error bound. Building on this, we propose a construction based on Berrut basis functions for computing multiple arbitrary functions and derive its approximation-error bound. We analyze the scaling of both bounds with the number of functions and the number of data points per function, and numerically compare the two constructions over a wide range of arbitrary functions. The results demonstrate that the proposed construction achieves lower relative errors than the existing approach in the tested settings.
Related
- Generalized Function-Correcting Partition Codes: Bounds and constructions
- Proof of the Riemann Hypothesis through the limit of an approximated ξ function
- Sunflower-Free Uniform Families: Recursive Constructions and Explicit Bounds
- Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
- Non-Separable Homothetic Triangles, Part I: Constructions and Lower Bounds
BibTeX
@misc{borah2026multiplefunction,
title = {{Multiple-Function Approximated Coded Computing: Constructions and Error Bounds}},
author = {Rimpi Borah and Wilton Kim and J. Harshan and Stanislav Kruglik and Han Mao Kiah},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16549},
eprint = {2610.16549},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16549},
}
RIS
TY - UNPB
TI - Multiple-Function Approximated Coded Computing: Constructions and Error Bounds
AU - Rimpi Borah
AU - Wilton Kim
AU - J. Harshan
AU - Stanislav Kruglik
AU - Han Mao Kiah
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.16549
UR - https://arxiv.org/abs/2610.16549
AB - Coded computing mitigates stragglers in distributed computation. While Lagrange coded computing (LCC) enables exact polynomial computation over finite fields, Berrut approximated coded computing (BACC) enables approximate computation of arbitrary, including non-polynomial, functions in the analog domain. In applications such as multi-task learning and inference, multiple functions must be evaluated over different subsets of a common dataset, making single-round computation desirable to reduce communication overhead. An existing LCC approach addresses this requirement but is restricted to polynomial functions over finite fields, leaving single-round multi-function computation in the analog domain an open problem. In this work, we develop a single-round construction for computing multiple arbitrary functions using BACC. We first extend the existing multi-function computation approach in LCC to the BACC setting and derive an approximation-error bound. Building on this, we propose a construction based on Berrut basis functions for computing multiple arbitrary functions and derive its approximation-error bound. We analyze the scaling of both bounds with the number of functions and the number of data points per function, and numerically compare the two constructions over a wide range of arbitrary functions. The results demonstrate that the proposed construction achieves lower relative errors than the existing approach in the tested settings.
ER -