Abstract:
A lossless bipartite vertex expander is a -left-regular bipartite graph such that for each subset of the left vertices which is not too large, the neighborhood of has size at least . 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.