In a recent work, S. Nitinawarat obtained a lower bound and an upper bound to the minimum list size in list decoding for arbitrarily varying multiple access channel (AVMAC), for which the capacity region of deterministic list codes has a non-empty interior. In the same paper, he proved that for a binary AVMAC, the minimum list size is finite, if and only if the capacity region of random correlated codes has a non-empty interior. A goal of this paper is to close the gap between the two bounds to the minimum list size. We find a necessary and sufficient condition for the list codes for an AVMAC to have a capacity region with a non-empty interior, in term of bipartite graphs. As a consequence, we determine the minimum list size. Moreover, we prove that for any AVMAC, the minimum list size is finite, if and only if its capacity region of random correlated codes has a non-empty interior.
Ning Cai received the B.S. degree in mathematics from the Normal College of Beijing, Beijing, China in 1982, the M.S. degree in mathematics from Academia Sinica, Beijing, China, in 1984, and the Dr. degree in mathematics from the University of Bielefeld, Bielefeld, Germany, in 1988.
During 1984-1986, he worked in the Institute of Systems Sciences, Academia Sinica, Beijing, China. During 1988-1989, he was with the Department of Mathematics, Statistics and Computer Science, the University of Illinois, Chicago, USA. From 1989 to 1998, he was a Wiss. Mitarbeiter in the Department of Mathematics, the University of Bielefeld, Germany and from 1998 to 1999, he was with the School of Computing, the National University of Singapore, Singapore. From 2000 to 2001, he was with the Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong. From 2002 to 2004 he was with the Department of Mathematics, the University of Bielefeld, Germany. In 2005 he visited Department of Information Engineering, The Chinese University of Hong Kong, Hong Kong. Since 2006, he is a distinguished professor in the State Key Lab of Integrated Services Networks (ISN), the Xidian University, China.
Dr. Cai is a recipient of the 2005 IEEE Information Theory Society Paper Award (for his paper “Linear network coding” co-authored with S.-Y. R. Li and R. W. Yeung).
Dr. Cai served as an IT Society Awards Committee member in 2008 and 2009, and a guest editor of joint Special Issue of IEEE Trans. on Information Theory and IEEE/ACM “on Networking on Networking Information Theory”, 2006. He has served on the committees of a number of information theory symposiums and workshops.
His research interests include network coding, information theory, and quantum information theory.
