About
Theoretical computer science research has led to the discovery (and revival) of several fundamental concepts in coding theory: locally testable codes, locally decodable codes, list-decodable codes, linear-time decodable codes, etc. The rich interplay of these concepts eventually led to the celebrated PCP theorem and a better understanding of hardness of approximation. High-dimensional expanders underlie, with the benefit of hindsight, constructions of error correcting codes that are locally testable (aka LTCs) as well as constructions of probabilistically checkable proofs (PCPs). High-dimensional expansion (HDX) is a generalization of expansion in graphs to higher dimensions, for example, hypergraphs or simplicial complexes. High-dimensional expansion is a relatively new topic of interest to a variety of areas in mathematics. Marvelous constructions of bounded-degree high-dimensional expanders rely on number theory and on group theory. Can these be useful towards constructions of new error correcting codes? Many constructions of codes are algebraic, harnessing the algebraic symmetries for designing decoding algorithms as well as establishing local testability. High-dimensional expansion provides a different – more geometric – angle for studying these phenomena.
This cluster will bring together experts on high-dimensional expansion and on coding theory with the goal of fostering interaction between the groups and together uncovering some of the potential of high-dimensional expansion. It will include a boot camp, which will teach the basics and acquaint participants with the key themes of the cluster.
This program is supported in part by the Patrick J. McGovern Foundation.
