Kai Zhang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Kai Zhang has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Chao Tian
Texas A&M University
4 shared publications - Jesus Gomez-Vilardebo
Centre Tecnològic de Telecomunicacions de Catalunya (CTTC/CERCA) Barcelona Spain
1 shared publication - Jia Tian
School of Automobile, Changan University, Xian, Shaanxi, China
1 shared publication - Ke Peng
Department of Medical Oncology, Zhongshan Hospital, Fudan University, Shanghai, China
1 shared publication - Lin Li
The George Washington University, Washington, DC, USA
1 shared publication - Shuo Shao
Department of System Science, University of Shanghai for Science and Technology, Shanghai, China
1 shared publication
Latest Publications
- 17 November 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69 (2) , 863-873
On the Fundamental Limits of Coded Caching Systems With Restricted Demand Types
Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. An information theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.
- 17 November 2020
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 69 (2) , 863-873
On the Fundamental Limits of Coded Caching Systems With Restricted Demand Types
Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. An information theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.
- 7 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 36 (6) , 1153-1164
Fundamental Limits of Coded Caching: From Uncoded Prefetching to Coded Prefetching
In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate of multiuser caching systems, various coding schemes have been proposed in the literature. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. While uncoded prefetching schemes in general offer order-wise optimal performance, coded prefetching schemes often have better performance at the low cache memory regime. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this paper, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is made, where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem.
- 7 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Communications
- Vol. 36 (6) , 1153-1164
Fundamental Limits of Coded Caching: From Uncoded Prefetching to Coded Prefetching
In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate of multiuser caching systems, various coding schemes have been proposed in the literature. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. While uncoded prefetching schemes in general offer order-wise optimal performance, coded prefetching schemes often have better performance at the low cache memory regime. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this paper, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is made, where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2087-2091
From Uncoded Prefetching to Coded Prefetching in Coded Caching Systems
In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate in multiuser caching systems, various coding schemes have been proposed. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this work, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is first given where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can in fact provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem. This inner bound does not have a closed form, but can be computed efficiently using a linear program.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2087-2091
From Uncoded Prefetching to Coded Prefetching in Coded Caching Systems
In order to characterize the fundamental limit of the tradeoff between the amount of cache memory and the delivery transmission rate in multiuser caching systems, various coding schemes have been proposed. These schemes can largely be categorized into two classes, namely uncoded prefetching schemes and coded prefetching schemes. The significant differences in the coding components between the two classes may leave the impression that they are largely unrelated. In this work, we provide a connection between the uncoded prefetching scheme proposed by Maddah Ali and Niesen (and its improved version by Yu et al.) and the coded prefetching scheme proposed by Tian and Chen. A critical observation is first given where a coding component in the Tian-Chen scheme can be replaced by a binary code, which enables us to view the two schemes as the extremes of a more general scheme. An explicit example is given to show that the intermediate operating points of this general scheme can in fact provide new memory-rate tradeoff points previously not known to be achievable in the literature. This new general coding scheme is then presented and analyzed rigorously, which yields a new inner bound to the memory-rate tradeoff for the caching problem. This inner bound does not have a closed form, but can be computed efficiently using a linear program.
- 28 September 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 66 (6) , 2396-2408
On the Symmetry Reduction of Information Inequalities
Information inequalities can be used to derive the fundamental limits of information systems. Many information inequalities and problem-specific constraints are linear equalities or inequalities of joint entropies, and thus outer bounding the fundamental limits can be viewed as and in principle computed through linear programming. However, for many practical engineering problems, the resultant linear program (LP) is very large, rendering such a computational approach almost completely inapplicable in practice. It was shown recently that symmetry can be used to effectively reduce the scale of the LP, however the precise amount of reduction was not well understood. In this study, we provide a method to pinpoint this reduction by counting the number of orbits induced by the symmetry on the set of the LP variables and the LP constraints, respectively. The Pólya counting theorem is a powerful tool for such counting task, which requires identifying the cycle index function. We propose a generic three-layer decomposition of the group structures for the quantities in typical information systems to facilitate such a calculation. Three problems are studied using this approach: extremal pairwise cyclically symmetric entropy inequalities, the regenerating code problem, and the caching problem, for which explicit formulae are provided for the cycle indices of the induced permutations.
- 28 September 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 66 (6) , 2396-2408
On the Symmetry Reduction of Information Inequalities
Information inequalities can be used to derive the fundamental limits of information systems. Many information inequalities and problem-specific constraints are linear equalities or inequalities of joint entropies, and thus outer bounding the fundamental limits can be viewed as and in principle computed through linear programming. However, for many practical engineering problems, the resultant linear program (LP) is very large, rendering such a computational approach almost completely inapplicable in practice. It was shown recently that symmetry can be used to effectively reduce the scale of the LP, however the precise amount of reduction was not well understood. In this study, we provide a method to pinpoint this reduction by counting the number of orbits induced by the symmetry on the set of the LP variables and the LP constraints, respectively. The Pólya counting theorem is a powerful tool for such counting task, which requires identifying the cycle index function. We propose a generic three-layer decomposition of the group structures for the quantities in typical information systems to facilitate such a calculation. Three problems are studied using this approach: extremal pairwise cyclically symmetric entropy inequalities, the regenerating code problem, and the caching problem, for which explicit formulae are provided for the cycle indices of the induced permutations.
- 13 January 2017
- Published by Springer Nature
- p. 62-71
A Novel PSO Based Task Scheduling Algorithm for Multi-core Systems
- 13 January 2017
- Published by Springer Nature
- p. 62-71
A Novel PSO Based Task Scheduling Algorithm for Multi-core Systems