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), Shai 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), Nati Linial (Hebrew University of Jerusalem), Alex Lubotzky (Hebrew University of Jerusalem), Roy Meshulam (Technion - Israel Institute of Technology), Izhar Oppenheim (Ben-Gurion University), Omer Reingold (Stanford University), Noga Ron-Zewi (Ben Gurion University), Atri Rudra (SUNY Buffalo), Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai), Amnon Ta Shma (Tel Aviv University), Luca Trevisan (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Avi Wigderson (Institute for Advanced Study), Mary Wootters (Stanford University), Gilles Zemor (Université de Bordeaux), David Zuckerman (University of Texas at Austin)

Visiting Graduate Students and Postdocs:
Siddharth Bhandari (TIFR), Michael Chapman (Hebrew University), Yotam Dikstein (Weizmann Institute of Science), Dean Doron (University of Texas at Austin), Fernando Granha Jeronimo (University of Chicago), Inbal Livni Navon (Weizmann Institute), Sai Vikneshwar Mani Jayaraman (University at Buffalo), Bharatram Rangarajan (Hebrew University), Shashank Srivastava (TTI Chicago), Yihan Zhang (Chinese University of Hong Kong), Minshen Zhu (Purdue University)

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).