Optimal Achievable Rates for Computation With Random Homologous Codes

 Building on the framework of nested coset codes, the optimal rate region for computing a linear combination of sources over a multiple access channel is studied. Inner and outer bounds on this optimal rate region are established when encoding is restricted to random ensembles of homologous codes, namely, structured nested coset codes from the same generator matrix and individual shaping functions based on typicality encoding. When the desired linear combination is ``matched'' to the structure of the multiple access channel, the inner and outer bounds coincide. This result indicates that existing coding schemes for computation based on random homologous code ensembles cannot be improved by using more powerful decoders, such as the maximum likelihood decoder. Using the proof techniques that we develop for analyzing codes under typicality encoding, the optimal rate region for broadcast channels with Marton coding is also characterized. The talk is concluded with a brief introduction to the dual of this problem: reverse compute-forward.

Joint-work with: Young-Han Kim (University of California, San Diego) and Sung Hoon Lim (Korea Institute of Ocean Science and Technology, Korea) This research was supported in part by the Electronics and Telecommunications Research Institute through Grant 17ZF1100 from the Korean Ministry of Science, ICT, and Future Planning and in part by the National Research Foundation (NRF) of Korea funded by the Ministry of Education, Science and Technology under Grant NRF-2017R1C1B1004192.