Past Meetup

Expander graphs and applications

This Meetup is past

13 people went

Location image of event venue

Details

Paper: https://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf

More info: https://upc.acm.org

Expander graphs and applications

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