Tata Institute of Fundamental Research

Construction of explicit lossless bipartite expanders

Student Seminar
Speaker: Sreejata Kishor Bhattacharya (TIFR)
Organiser: Varun Ramanathan
Date: Friday, 29 Sep 2023, 16:00 to 17:00
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)

A $D,\epsilon$ lossless bipartite vertex expander is a $D$-left-regular bipartite graph such that for each subset $S$ of the left vertices which is not too large, the neighborhood of $S$ has size at least $(1-\epsilon)|S|$. Lossless expanders are important because of their usage in construction of linear time decodable error correcting codes (Sipser-Spielman codes). In this talk, we shall describe the first explicit construction of lossless expanders by Capalbo, Wigderson et al.