Sipser-Spielman expander codes are a variant of Tanner codes defined on expander graphs by placing code bits on edges and assigning a small linear code with sufficiently large distance to each vertex, constraining the bits on the connected edges. Expander codes are essential in coding theory since they provide explicit families of asymptotically good classical LDPC codes with very simple linear time decoding. Recent constructions of asymptotically good classical LTCs and qLDPC codes have motivated the study of generalizations of Sipser-Spielman codes defined on high-dimensional expanders (HDXs) instead of expander graphs. Toward this goal, it was proposed recently by several researchers to extend the theory of simplicial HDXs over GF(2) to a much more general context of high-dimensional cell complexes (simplicial, cubical, polyhedral, etc.) with arbitrary local systems of abelian groups attached to them. Such objects, also known as cellular sheaves, have been studied in algebraic topology since 1960s and have found many interesting applications in computer science and coding theory in the last decade. By replacing the standard Hamming weight, counting the non-zero coefficients over GF(2), with the block Hamming weight, counting the non-zero coefficients over abelian groups one can naturally extend all the standard definitions from the theory of simplicial HDXs over GF(2) (local minimality, coboundary expansion, Cheeger constants, etc.) to the general context of cellular sheaves. In this talk, I plan to focus on the coboundary expansion in the links of products of expander codes and its pivotal role in the constructions of good LTCs and qLDPC codes. The talk is based on the joint recent works with Gleb Kalachev.
Copyright. All Rights Reserved.