Construction of explicit lossless bipartite expanders

Speaker:
Sreejata Kishor Bhattacharya
Organiser:
Varun Ramanathan
Date:
Friday, 29 Sep 2023, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
Category:
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.