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,ϵ 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ϵ)|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.