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), Shay Evra (IAS), Yuval Filmus (Technion - Israel Institute of Technology), Elena Grigorescu (Purdue University), Venkat Guruswami (Carnegie Mellon University), Prahladh Harsha (TIFR), Tali Kaufman (Bar-Ilan University), Alexander Lubotzky (Hebrew University of Jerusalem), Roy Meshulam (Technion - Israel Institute of Technology), Izhar Oppenheim (Ben-Gurion University), Noga Ron-Zewi (Ben Gurion University), Atri Rudra (SUNY Buffalo), Madhu Sudan (Harvard University), Amnon Ta Shma (Tel Aviv University), Luca Trevisan (UC Berkeley), Avi Wigderson (Institute for Advanced Study), Mary Wootters (Stanford University), Sergey Yekhanin (Microsoft Research), Gilles Zemor (Université de 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).