  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 (FRS) 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 in order to obtain the side information. This side
information will be then utilized to prune the output of list decoder in order
to uniquely recover the true outcome. We further propose folded Lagrange coded
computing, referred to as folded LCC or 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 compared to that of LCC.
