The game of coding framework was introduced to extend coding-theoretic recovery beyond its traditional limit, under which the number of honest reports must exceed the number of adversarial or corrupted reports. It does so by exploiting the rational behavior of adversarial participants and their incentive to keep the system live. Existing game-of-coding formulations, however, assume that the adversarial-noise distribution is independent of the realized ground-truth computation. This assumption may be restrictive when an informed adversary can adapt its reports to the value being computed. In this paper, we study the game of coding with input-dependent adversarial noise. We introduce a unified multi-node, multidimensional formulation. For every family of conditional adversarial-noise distributions, we construct an input-independent joint noise distribution, and prove that this reduction exactly preserves the probability of acceptance and the accepted mean-squared estimation error. Consequently, the input-dependent and input-independent models have identical achievable performance regions, and the same equilibrium utilities.
Hanzaleh Akbari Nodehi, M. Maddah-ali· 0 citations
Existing coded-computing designs do not explicitly exploit the intrinsic structure of the input data. In communication systems, statistical structure and redundancy are often removed through source coding (or compression) before channel coding is applied. This principle, however, does not transfer directly to coded computation. In many computational tasks, particularly in machine learning, the structure of the data is precisely what the computation seeks to exploit to infer outputs or learn meaningful patterns. Consequently, coded-computing schemes should preserve and leverage this structure in their code design, rather than ignoring or eliminating it through source coding. This observation motivates a different perspective on code construction. In many channel-coding schemes, such as Reed-Solomon codes, coded symbols are generated by evaluating a low-dimensional algebraic representation at selected points. In contrast, many high-dimensional datasets naturally concentrate near low-dimensional manifolds. In this paper, we exploit this intrinsic geometry by designing coded samples that follow the natural manifold of the data, rather than imposing an artificial low-dimensional structure unrelated to the data distribution. Inspired by graph-based manifold learning, we propose a manifold-aware encoding strategy for general coded computing (GCC). Experiments on neural network inference and high-dimensional polynomial evaluation demonstrate that the proposed strategy consistently and significantly reduces the mean squared recovery error under straggling compared with standard GCC.
