High Dimensional Expansion and Error Correcting Codes

High dimensional expansion generalizes edge and spectral expansion in graphs to higher dimensional hypergraphs or simplicial complexes. Unlike for graphs, it is exceptionally rare for a high dimensional complex to be both sparse and expanding. The only known such expanders are number-theoretic or group-theoretic.

Their key feature is a local-to-global geometry, that allows deducing global information about the entire complex from local information in the neighborhoods / links. We will discuss some results known about these objects, and how their local-to-global geometry, shared also by PCPs, can potentially lead to new codes and proofs.

Date

Affiliation

Weizmann Institute of Science; Visiting Professor, School of Mathematics