题目：High-rate storage codes on triangle-free graphs

主讲人：Alexander Barg

时间：2022年04月21日09:00-10:00

地址：ZOOM ID：845 5661 2221 Password：689771

摘要：Consider an assignment of bits to the vertices of a connected graph G(V,E) with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length |V| on G. If G contains many cliques, it is easy to construct storage codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where finding codes of rate >1/2 is a nontrivial task. Previously only isolated examples of storage codes of rate ≥ 1/2 on triangle-free graphs were given in the literature. The class of graphs that we consider is coset graphs of linear binary codes (Cayley graphs of the group F_2^r). One of the main results of this work is an infinite family of linear storage codes with rate approaching 3/4. We also give a group of necessary conditions for such codes to have rate potentially close to 1 and state a number of open problems. Joint work with Gilles Zémor.

主讲人简介： Alexander Barg (Fellow, IEEE) is currently a Professor with the Department of Electrical and Computer Engineering, Institute for Systems Research, University of Maryland, College Park, MD, USA. He is broadly interested in information and coding theory, applied probability, and algebraic combinatorics, and has published about a hundred research papers. He received the 2015 Information Theory Society Paper Award, was a plenary speaker at the 2016 IEEE International Symposium on Information Theory (Barcelona, Spain), and has served as the Editor-in-Chief (2018–2019) of IEEE Transactions on Information Theory.

邀请人：胡思煌

审核人：魏普文