[PWL] Expander graphs and applications

Oriol serra, chair of the Departament de Matemàtiques at UPC, will talk about Expander graphs and its applications.

Slides of the presentation here.

Expanding graphs grew up in the context of communication networks. The notion of expansion is related to the growth of neighborhoods of sets in graphs and it is so natural that it found its place in a wide area of applications, some of them unexpected, in computer science, statistics and mathematics. The aim of the talk is to describe some of these applications in computation, random walks and in error correcting codes. A probabilistic argument shows that expander graphs are abundant, but explicit constructions turn out to be connected to sophisticated mathematical tools, which will be only summarized in the talk.

Nowadays there is a rich literature on the topic. The talk is based on the excellent survey :

Shlomo Hoory, Nathan Linial and Avi Widgerson, Expander Graphs and their applications, Bulletin of the AMS Volume 43, Number 4, October 2006, Pages 439–561

Date: 25th of April, 12:00 PM

Location: UPC FIB, Building A5, Room 202