On Expansion, High-Dimensional Expanders, and Applications in Coding Theory

Abstract

Communication protocols and data storage necessitate the use of error-correcting codes, which inject redundancy into a bit-string to make it resilient against corruption. Desirable properties of such codes include distance (ensuring recoverability of the original message) and rate (capturing transmission efficiency). It is well known that expander graphs—sparse yet highly connected graphs—can be used to construct codes that achieve strong trade-offs between these parameters. Furthermore, the higher dimensional analog of expanders, high dimensional expanders, have also found useful applications in coding theory. Thus, this thesis studies this intersection of expanders, high dimensional expanders, and coding theory. Thematically, this paper can be viewed in two parts: the first is a survey of classical and recent ideas in this area, and the second presents our contributions, which are new combinatorial constructions of expanding square and cubical complexes.

The survey component of this paper begins by introducing foundational concepts from both areas. We begin by exploring simple trade-offs between distance and rate via the Singleton bound and Gilbert-Varshamov bound. We then discuss key constructions in coding theory such such as Hadamard codes, Reed-Solomon codes, Reed-Muller codes, and tensor codes—and discuss known trade-offs among parameters like distance, rate, and locality. Following this, we explore the spectral and combinatorial properties of expander graphs and how they enable the construction of codes with good parameters. This naturally leads to a discussion of highdimensional expanders (HDXs), including square and cubical complexes, and how they have been used to build codes that have constant rate, distance, and locality (in particular, the codes of [DEL+22]).

The second component of the paper presents our original contributions: new combinatorial constructions of expanding square and cubical complexes. For our construction of square complexes, we are able to characterize the expansion of classical and parallel random walks. For cubical complexes, we propose a general construction in arbitrarily high dimensions and examine its structural features, potential expansion properties, and the technical challenges it raises.