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