|
Lecturer: Dr. Maurice Cochand
Assistant: Jan Volec
This year's course will cover the theory of expanders. Expanders are very well connected graphs with only few edges, which can be used as cheap substitutes for complete graphs. The first construction of infinite families of expanders of bounded degree is rather recent, and they have applications in very diverse fields like complexity theory, error correcting codes, pseudo-randomness, embedding of finite metric spaces. After reviewing some constructions of expanders, we will discuss such applications, which should illustrate the richness of Mathematics motivated by problems in Theoretical Computer Science.
Exercises:
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information