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


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

Long-Term Participants (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 (Tata Institute of Fundamental Research), 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), Nikhil Srivastava (UC Berkeley), Amnon Ta-Shma (Tel Aviv University), Luca Trevisan (UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Uli Wagner (IST Austria), Mary Wootters (Stanford University), Gilles Zemor (Université de Bordeaux), David Zuckerman (University of Texas at Austin)

Visiting Graduate Students and Postdocs:

Vedat Alev (University of Waterloo), 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), Sai Vikneshwar Mani Jayaraman (University at Buffalo), Bharatram Rangarajan (Hebrew University), Shashank Srivastava (TTI Chicago), Pascal Wild (IST Austria), Yihan Zhang (Chinese University of Hong Kong), Minshen Zhu (Purdue University)


Thursday, Jul. 11Friday, Jul. 12, 2019


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

Past Internal Program Activities

Thursday, August 8th, 10:00 am12:00 pm
Tuesday, August 6th, 10:00 am11:30 am
Shai Evra (IAS)
Thursday, August 1st, 10:00 am11:00 am
David Zuckerman
Tuesday, July 30th, 2:00 pm3:30 pm
Avi Wigderson (IAS)
Tuesday, July 30th, 10:00 am11:00 am
Yuval Filmus
Monday, July 29th, 2:00 pm3:30 pm
Prahladh Harsha
Monday, July 29th, 10:00 am11:00 am
Siqi Liu
Thursday, July 25th, 10:00 am11:30 am
Madhur Tulsiani
Tuesday, July 23rd, 11:00 am11:45 am
Michael Chapman
Tuesday, July 23rd, 10:00 am10:45 am
Noga Ron Zewi