Matroidal Entropy Functions: A Quartet of Theories of Information, Matroid, Design, and Coding

Prof. CHEN Qi
Xidian University, China
Hosted by Department of Information Engineering, CUHK
Thursday, 20 April, 2023
Room 801, Ho Sin Hang Engineering Building

A matroidal entropy function is an entropy function in the form log v‧rM, where v is an integer exceeding one and rM is the rank function of a matroid M. For a matroid M, the characterization of matroidal entropy function induced by M is to determine its probabilistic-characteristic set χM, i.e., the set of integers v such that log v‧rM is entropic. To characterize matroidal entropy functions, we introduce variable strength orthogonal arrays(VOA), which can be considered as special cases of classic combinatorial structure orthogonal arrays(OA). We prove that whether log v‧rM is entropic depends on whether a VOA(M, v) is constructible. Leveraging the correspondences between matroidal entropy functions and VOAs, we characterize the matroidal entropy functions induced by matroids obtained from matroid operations such as deletion, contraction, minor, serize and parallel connection and 2-sum. Utilizing these results, we characterize two classes of matroidal entropy functions, i.e., those induced by regular matroids and matroids with the same p-characteristic set as uniform matroid U2,4. As the support of characterizing random vector of a matroidal entropy function, i.e., the set of rows of the corresponding VOA is equivalent to the code book of an almost affine code, they can be applied to solve coding problems in secret sharing, network coding, index coding and locally repairable code.


Qi Chen received his PhD degree at Information Engineering Department, The Chinese University of Hong Kong in 2014. From 2014 to 2017, He was a post-doctoral fellow at Institute of Network Coding and Information Engineering Department, The Chinese University of Hong Kong . From Sept. 2015 to Jan. 2016, he was also a postdoc at ECE department, Drexel University. In 2018, he joined State Key Laboratory of Integrated Services Networks and School of Telecommunication Engineering, Xidian University, Xi’an, China, where he is now an associate professor. His research interests include information theory and related areas, in particular, the characterization of the entropy region.