Partially Connected Networks: Limits, Algorithms, and Applications in Wireless Distributed Computing

This talk is divided into two parts. In the first part, we present a general interference alignment (IA) coding scheme for general partially-connected interference networks and formulate an intuitive number-filling puzzle corresponding to a given network. The score of the puzzle solution determines the optimal sum degrees of freedom achievable by the IA scheme.

In the second part, we turn to wireless distributed computing (DC) systems, particularly those based on the MapReduce framework. In such systems, communication bottlenecks arise due to the shared and interference-prone nature of wireless channels. We demonstrate that wireless DC systems exhibit strong structural parallels with partially connected networks. Leveraging these parallels, we apply the coding techniques from the first part to significantly improve the computation-communication tradeoff. Finally, we present an information-theoretic converse bound, establishing that the achieved tradeoff is nearly optimal.

Yue Bi received his B.Eng. degree in Information Engineering and his M.Eng. degree in Electronics and Communication Engineering from Shanghai Jiao Tong University in 2017 and 2020, respectively. He was recognized as an excellent graduate of Shanghai Jiao Tong University for his bachelor’s thesis and as an excellent graduate of Shanghai for his master’s thesis. He obtained a double Ph.D. degree from Télécom Paris, Institut Polytechnique de Paris, and the School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University. He is currently a postdoctoral researcher at Télécom Paris. His research interests include wireless communication, distributed computation and estimation, and information theory.