Summer 2019

Summer Cluster: Error-Correcting Codes and High-Dimensional Expansion

Jul. 11Aug. 9, 2019

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 underly, 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.

sympa [at] lists [dot] simons [dot] berkeley [dot] edu (body: (Click here to subscribe to our announcements email list for this program).

Irit Dinur (Weizmann Institute), Prahladh Harsha (Tata Institute of Fundamental Research)

List of participants (tentative list, including organizers):
Irit Dinur (Weizmann Institute of Science), Shai Evra (Institute for Advanced Study, Princeton), Yuval Filmus (Technion University), Venkat Guruswami (Carnegie Mellon University), Prahladh Harsha (Tata Institute of Fundamental Research), Tali Kaufman (Bar-Ilan University), Swastik Kopparty (Rutgers University), Nati Linial (Hebrew University), Alex Lubotzky (Hebrew University), Roy Meshulam (Technion), Izhar Oppenheim (Ben-Gurion University of the Negev), Omer Reingold (Stanford University), Noga Ron-Zewi (Haifa University), Atri Rudra (State University of New York), Shubangi Saraf (Rutgers University), Madhu Sudan (Harvard University), Amnon Ta-Shma (Tel Aviv University), Avi Wigderson (Institute for Advanced Study, Princeton), Mary Wooters (Stanford University), Sergey Yekhanin (Microsoft Research), Gilles Zemor (University of Bordeaux), David Zuckerman (University of Texas at Austin)

Those interested in participating in this program should send an email to the organizers at this ecc2019 [at] lists [dot] simons [dot] berkeley [dot] edu (at this address).