Analog Lagrange Coded Computing for Privacy-Preserving Floating-Point Distributed Computation
Algorithms AIMech:AnalogLagrangeCodedComputingForPrivacyPreservingFloatingPointDistributedComputation DRAFT
Aliases: Analog Lagrange Coded Computing, ALCC, Complex Roots-of-Unity Analog Lagrange Coded Computing
An analog coded distributed computing algorithm that extends Lagrange Coded Computing from finite fields to real and complex floating-point domains by embedding K real-valued dataset partitions X_1, ..., X_K and T zero-mean Gaussian random noise masks Z_1, ..., Z_T into a degree-(K + T - 1) Lagrange interpolation polynomial u(z) evaluated at complex roots of unity beta_j = gamma * omega^(j-1) and distributed to N worker nodes at unit-circle roots of unity alpha_i = omega_N^i, enabling numerically stable recovery of degree-D polynomial evaluations f(X_j) from any D*(K + T - 1) + 1 surviving workers while bounding mutual-information and differential-privacy leakage against up to T colluding workers.
Identity Notes & Concept Scope
Introduced as Analog Lagrange Coded Computing (ALCC) by Mahdi Soleymani, Hessam Mahdavifar, and A. Salman Avestimehr (IEEE Journal on Selected Areas in Information Theory, Vol. 2, No. 1, pp. 283-295, 2021; arXiv:2008.08565). Distinct from finite-field Lagrange Coded Computing (Yu et al., AISTATS 2019, Round 536), which requires fixed-point quantization into F_p and suffers from modular overflow on multi-term products; distinct from Berrut Approximated Coded Computing (Jahani-Nezhad & Maddah-Ali, IEEE TPAMI 2023, Round 547), which uses barycentric rational interpolation for non-polynomial functions without T-colluding Gaussian privacy masks; and distinct from CodedPrivateML (So, Guler, & Avestimehr, IEEE JSAIT 2021, Round 550), which uses stochastic rounding into a prime finite field F_p rather than analog floating-point complex roots of unity.
Claims & Grounded Evidence
4 Claims
Mechanism
#alcc-complex-roots-of-unity-lagrange-encoding-mechanism
ALCC encodes K real-valued dataset blocks X_1, ..., X_K in R^(m x d) together with T i.i.d. Gaussian noise matrices Z_1, ..., Z_T ~ N(0, sigma_n^2) into the complex Lagrange polynomial u(z) = sum_{j=1}^K X_j l_j(z) + sum_{j=K+1}^{K+T} Z_{j-K} l_j(z) using evaluation points beta_j = gamma * exp(2*pi*i*(j-1)/(K+T)) on a circle of radius gamma in C and worker points alpha_r = exp(2*pi*i*r/N) on the unit circle, so that any subset of at least D*(K + T - 1) + 1 workers evaluating a degree-D polynomial f(u(alpha_r)) suffices to interpolate f(X_j) with well-conditioned complex Vandermonde matrices.
Scope
#alcc-analog-privacy-leakage-tradeoff-scope
Against any subset T_c of at most T colluding workers in the analog floating-point domain, ALCC bounds the mutual-information leakage I(X; U_{T_c}) and provides (epsilon, delta)-differential privacy guarantees as an explicit function of the noise variance sigma_n^2, the circle radius ratio gamma, and the singular values of the complex Cauchy-Vandermonde submatrices.
Limitation
#alcc-accuracy-privacy-floating-point-precision-limitation
Unlike finite-field Lagrange coding which achieves zero mutual information (perfect information-theoretic privacy) over F_p, ALCC over floating-point numbers exhibits a fundamental accuracy-privacy trade-off because increasing the Gaussian mask standard deviation sigma_n to strengthen privacy amplifies floating-point roundoff error in the decoded polynomial evaluation.
Application
#alcc-privacy-preserving-distributed-polynomial-inference-application
Applied to privacy-preserving straggler-resilient distributed matrix multiplication and polynomial kernel classification over floating-point datasets without finite-field quantization.
⚠️ Curated Limitations & Negative Results
- Requires complex arithmetic over roots of unity whenever real evaluation nodes would induce exponentially growing Vandermonde condition numbers.
- Subject to a fundamental precision-privacy trade-off where large Gaussian mask variance degrades floating-point mantissa accuracy.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:FederatedLearning
Federated Learning
|
related_match | AIO:FederatedLearning covers collaborative distributed learning paradigms, whereas ALCC is a specific complex-roots-of-unity Lagrange coded computing protocol for privacy-preserving straggler-resilient floating-point polynomial evaluation. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r548-primary-pdf
|
Mahdi Soleymani, Hessam Mahdavifar, A. Salman Avestimehr
|
primary paper
full_text
|
ID: https://dblp.org/rec/journals/jsait/SoleymaniMA21
sha256:cdf28d59fe6c…
|
r548-arxiv-abs
|
Mahdi Soleymani, Hessam Mahdavifar, A. Salman Avestimehr
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2008.08565
sha256:e9df90efcd68…
|
r548-metadata-cr
|
Mahdi Soleymani, Hessam Mahdavifar, A. Salman Avestimehr
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/journals/jsait/SoleymaniMA21
sha256:02c3e13ceba1…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T10:31:00Z
Updated: 2026-10-19T10:31:00Z
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories