  Multi-party computation (MPC) is promising for designing privacy-preserving
machine learning algorithms at edge networks. An emerging approach is coded-MPC
(CMPC), which advocates the use of coded computation to improve the performance
of MPC in terms of the required number of workers involved in computations. The
current approach for designing CMPC algorithms is to merely combine efficient
coded computation constructions with MPC. We show that this approach fails
short of being efficient; e.g., entangled polynomial codes are not necessarily
better than PolyDot codes in MPC setting, while they are always better for
coded computation. Motivated by this observation, we propose a new
construction; Adaptive Gap Entangled (AGE) polynomial codes for MPC. We show
through analysis and simulations that MPC with AGE codes always perform better
than existing CMPC algorithms in terms of the required number of workers as
well as computation, storage, and communication overhead.
