# List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier

arXiv: https://arxiv.org/abs/2101.11653 · HTML: https://mlsanity.com/paper/2101.11653/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 62 references that are in the map.
- First posted on arXiv 27 Jan 2021.

## Builds on (most cited first, 21 of 21)

- [Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning](https://mlsanity.com/paper/2002.04156/) (2020)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [Coded Computing for Low-Latency Federated Learning over Wireless Edge Networks](https://mlsanity.com/paper/2011.06223/) (2020)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [A Scalable Approach for Privacy-Preserving Collaborative Machine Learning](https://mlsanity.com/paper/2011.01963/) (2020)
- [CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning](https://mlsanity.com/paper/1902.00641/) (2019)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [Analog Lagrange Coded Computing](https://mlsanity.com/paper/2008.08565/) (2020)
- [Coded Computation over Heterogeneous Clusters](https://mlsanity.com/paper/1701.05973/) (2017)
- [A Unified Coding Framework for Distributed Computing with Straggling Servers](https://mlsanity.com/paper/1609.01690/) (2016)
- [A Unified Coded Deep Neural Network Training Strategy Based on Generalized PolyDot Codes for Matrix Multiplication](https://mlsanity.com/paper/1811.10751/) (2018)
- [Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier](https://mlsanity.com/paper/2001.05101/) (2020)
- [Edge Computing in the Dark: Leveraging Contextual-Combinatorial Bandit and Coded Computing](https://mlsanity.com/paper/1912.09512/) (2019)
- [Distributed Matrix-Vector Multiplication: A Convolutional Coding Approach](https://mlsanity.com/paper/1901.08716/) (2019)
- [Collaborative Decoding of Polynomial Codes for Distributed Computation](https://mlsanity.com/paper/1905.13685/) (2019)
- [Numerically Stable Binary Gradient Coding](https://mlsanity.com/paper/2001.11449/) (2020)
- [Privacy-Preserving Distributed Learning in the Analog Domain](https://mlsanity.com/paper/2007.08803/) (2020)
- [Coding for Distributed Fog Computing](https://mlsanity.com/paper/1702.06082/) (2017)
- [Coded Distributed Computing: Performance Limits and Code Designs](https://mlsanity.com/paper/1906.10105/) (2019)

## Built on by (most cited first, 4 of 4)

- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Adaptive Verifiable Coded Computing: Towards Fast, Secure and Private Distributed Machine Learning](https://mlsanity.com/paper/2107.12958/) (2021)
- [ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment](https://mlsanity.com/paper/2302.09913/) (2023)
- [Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation](https://mlsanity.com/paper/2204.11168/) (2022)

## Abstract (arXiv)

We consider the problem of coded computing, where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. The workload of computing this side information is negligible compared to the computations done by each worker. This side information is then utilized to prune the output of the list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two asymptotically compared to that of LCC.