List-Decodable Coded Computing: Breaking the Adversarial Toleration
  Barrier
  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.
