High dimensional expanders (HDX)
and
Error Correcting Codes

Spring 2023

Organized by Irit Dinur and Alex Lubotzky
Location: Goldsmith 208
Time: Wednesdays 14:30 - 16:30 (first meeting 19 April, 2023)

High dimensional expansion seems related, empirically, to the structure of constraints in some of the most popular error correcting codes. In the seminar we will explore high dimensional expansion in itself, and in relation to error correcting codes. Along the way we will learn about exciting new developments in this area.

Here is a tentative plan / list of topics we might cover in the seminar:

1. Introduction (Irit 19/4:): how to define an error correcting code on a high dimensional expander [paper]
   
   
2. (Alex Lubotzky 27/4:) Coboundary expansion and property testing [pdf]
   
   
3. (Yotam Dikstein 3/5:) Coboundary and cosystolic expansion [Notes]
   
   
4. (Uriya First 10/5:) Codes as sheaves over simplicial complexes [paper]
   
   
5. (Elad Tsalik 17/5:) Cohomology on the finite-field Grassmannian
   
   
6. (Devika Sharma 24/5) Quantum low density parity check codes [notes] [paper1] [paper2]
   
   
7. (Nir Magrafta 31/5) Robust testability of tensor codes [paper] and [paper]
   
   
8. (Liad & Dvir 7/6) Direct Sum Testing [paper]
   
   
9. (Yotam Dikstein 14/6) super sampling in high dimensional expanders
   
   
10. (Shachar Meir and Itamar Shoshani 21/6) The Kikuchi matrix and lower bounds on locally decodable codes [paper1] [paper2]
    
    
11. (Vadim Grinberg 5/7) Topological overlap [paper]
    
    
12. (Ziv Bakhajian 12/7) Approximate covers of simplicial complexes [paper]
    
    

---

13. (List Decoding Tensor Products and Interleaved Codes [paper]
    
    
14. Agreement Testing [paper]
    
    
15. Low degree tests and expansion of the Grassmann [paper]