CS Paper Radar

Multiple-Function Approximated Coded Computing: Constructions and Error Bounds

Rimpi Borah, Wilton Kim, J. Harshan, Stanislav Kruglik, Han Mao Kiah

cs.IT ·submitted 2026-10-12 10:30 UTC · v2

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.

Comment
11 pages in two-column format. This updated version contains proofs of Theorem 1, Theorem 2 and Lemma 1 in Appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting

cs.LG ·2026-08-28 ·Parsa Moradi, Behrooz Tahmasebi, Mohammad Ali Maddah-Ali
theory similarity 0.62
Abstract

Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems. However, existing coded-computing schemes are predominantly designed for the exact recovery of highly structured computations, such as polynomial evaluation and matrix multiplication, and typically rely on strict recovery thresholds. These assumptions significantly limit their applicability to modern machine-learning workloads, particularly deep neural networks (DNNs), whose computations generally lack rigid algebraic structure and, in many applications, require only accurate approximations rather than exact recovery. To address this gap, we revisit coded computing from a learning-theoretic perspective and introduce General Coded Computing (GCC). Rather than adopting existing algebraic tools, GCC formulates coded computing through a natural end-to-end mean-squared error loss that directly measures the discrepancy between the desired computations and their recovered estimates. By deriving suitable upper bounds and restricting the encoder and decoder to a reproducing kernel Hilbert space (RKHS) with mild smoothness constraints, we show that both the encoder and decoder admit specific representations as linear combinations of RKHS kernel functions. This representation allows the corresponding coefficients to be computed efficiently. Moreover, this framework enables us to establish theoretical performance guarantees for GCC under two complementary straggler regimes. In the worst-case setting with $N$ worker nodes, and at most $S$ stragglers, we show that the end-to-end loss decays at least at rate $O(S^3N^{-3})$ for standard configurations. We then study a probabilistic setting in which each worker independently straggles with probability $p$. We prove that the expected loss can still converge at rate $O(\log_{1/p}^3(N)N^{-3})$.

0.44

Plotkin-type Bound on Function-Correcting Codes for Monomial Mappings

cs.IT ·2026-10-03 ·Kanchana Lokshmii Jagatti, B. Sundar Rajan
published similarity 0.59
Abstract · Proceedings of IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), 2026 (To appear)

Function-correcting codes, recently introduced by Lenz et al.\ (2023), provide a framework for the receiver to provide a higher level of protection against channel errors than the level of protection for messages. In this paper, we derive a generalised Plotkin-type bound on the redundancy of FCCs under the Hamming metric for arbitrary functions over finite fields. The proposed bound recovers the classical Plotkin bound for classical error-correcting codes as a special case. We further obtain explicit Plotkin-type bounds for linear functions, Hamming-weight functions, and Hamming-weight threshold functions. In addition, we study FCCs for monomial mappings $f(x)=x^n$ over $\mathbb{F}_{q^k}$, which are widely utilised in coding theory, cryptography, and finite geometry, and derive an explicit Plotkin-type redundancy bound.

0.14

Basis Selection For Analog Coded Computing Under Differential Privacy Constraints

cs.IT ·2026-10-19 ·Aaditya Sharma, Rimpi Borah, J. Harshan
similarity 0.57
Abstract

In analog coded computing, encoding basis functions are typically chosen to guarantee exact reconstruction and improve numerical stability. However, the same basis functions also determine the statistical geometry of the observations available to colluding workers, and hence directly influence the privacy of the underlying data. This suggests that basis selection should not be viewed solely as a reconstruction or numerical conditioning problem, but rather as a joint privacy and accuracy co-design problem. Motivated by this observation, we revisit Analog Lagrange Coded Computing (ALCC) and show that the full orthogonality constraints imposed by the conventional Lagrange basis are stronger than what is required for exact recovery. We retain only the interpolation constraints necessary for the data bearing basis functions and require the noise bearing basis functions merely to vanish at the data recovery points. This yields a parameterized family of generalized polynomial encoding bases that preserves exact reconstruction while introducing additional design degrees of freedom. We then derive a basis-dependent characterization of differential privacy for colluding workers and formulate a privacy-calibrated numerical optimization problem that jointly selects the data and noise basis functions to reduce reconstruction error while satisfying a prescribed \((ε,δ)\)-DP requirement. The resulting framework therefore treats the encoding basis itself as a privacy-design variable, rather than selecting a fixed closed-form basis a priori. The same design philosophy is also compatible with alternative privacy metrics such as mutual-information leakage. Numerical results show that, at the same privacy level, optimized basis functions substantially reduce floating-point reconstruction error relative to conventional ALCC.

0.29

Hamming Ideals and Grobner Bases for ISD-like Syndrome Decoding

cs.CR cs.SCmath.AC ·2026-09-16 ·Roberto La Scala, Marco Marchesin, Sharwan K. Tiwari
similarity 0.57
Abstract · 30 pages

We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric functions. Since these equations may have high degree, we exploit convolution identities for elementary symmetric functions, together with factorizations based on Lucas' identity, to derive an equivalent formulation with auxiliary variables and equations of bounded degree. Building on this modeling, we generalize the ISD paradigm through an ISD-like decoding strategy, implemented by the GBDecode algorithm, in which only a subset of an information set is fixed. This approach reduces the size of the combinatorial search space at the cost of solving the associated multivariate nonlinear systems. To handle this algebraic component, we employ the MultiSolve algorithm, which replaces a single Grobner basis computation with a collection of computations on simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. This provides a tunable balance between combinatorial search and algebraic solving. We evaluate the resulting approach experimentally on instances of the Syndrome Decoding Problem for random binary linear codes, using parameters corresponding to the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. The experiments assess the feasibility of this combinatorial-algebraic approach and provide insights into the practical behavior of Grobner basis techniques within an ISD-like decoding framework.

0.32

On Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.57
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

Optimal Convergence of Iterative Methods for Datalogo

cs.DS ·2026-10-02 ·Simon Frisk, Sungjin Im, Paraschos Koutris, Benjamin Moseley, Hung Ngo +2 more
theory similarity 0.56
Abstract

$\mathsf{Datalog}^\circ$ has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization techniques such as semi-naïve evaluation and demand transformation. $\mathsf{Datalog}^\circ$ accomplishes this by generalizing the {\em or} and {\em and} operators of Datalog to addition and multiplication over a semiring. Finding a (minimal) fixpoint of a $\mathsf{Datalog}^\circ$ program is equivalent to finding a solution to a system of polynomial equations over the underlying semiring. Solving these systems of polynomial equations is not only a fundamental problem in the theory of $\mathsf{Datalog}^\circ$, but also has many applications in computer science, such as in databases, program analysis, and optimization. This paper resolves a key open problem in the theory of $\mathsf{Datalog}^\circ$: we prove a tight upper bound on the number of steps until convergence of iterative methods for solving these polynomial equation systems over a commutative $p$-stable semiring. In particular, we show that the number of steps until convergence is $O((p+1)n)$ where $n$ is the output size of the $\mathsf{Datalog}^\circ$ program. As the number of steps until convergence is only a proxy for the runtime of $\mathsf{Datalog}^\circ$ evaluation, we also consider the number of semiring operations used and show that, for a natural class of algorithms, $O((p+1)mn)$ is a tight upper bound, where $m$ is the maximum number of semiring operations per iteration.

0.29

Function Inversion Reporting

cs.DS ·2026-11-09 ·Itai Dinur, Alexander Golovnev, Chao Yan, Yiding Zhu
similarity 0.56
Abstract

In the Function Inversion problem, the goal is to invert a function $f:[N] \to [N]$ in two phases. In the preprocessing phase, the offline algorithm computes an advice string of length $S$ bits. In the online phase, the online algorithm receives the advice and a challenge $y \in [N]$, and the goal is to find a preimage $x \in [N]$ such that $f(x) = y$ in time $T$. The problem was initially studied in cryptography, but in recent years it has found various applications to data structure problems. Yet, several of the applications require a variant of Function Inversion, known as Function Inversion Reporting, where the goal is to output all preimages of the challenge $y$. In this paper, we study the Function Inversion Reporting problem in a systematic way by unifying and improving existing algorithms. As a result, we obtain improved data structures for several problems including 3SUM-Indexing Reporting, Range Reporting, Approximate Nearest Neighbor, Jumbled Indexing Reporting, and Gapped String Indexing Reporting.

0.19

Graph-Theoretic Bounds for Non-Linear Function Computation Broadcast

cs.IT ·2026-10-06 ·Derya Malak, Vijith Kumar K. P., M. Reza Deylam Salehi
publishedtheory similarity 0.56
Abstract · This work extends the conference version presented at IEEE ISIT 2025, available at https://arxiv.org/abs/2502.13688. Example 2, concerning t…

This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.

0.48