printlogo
http://www.ethz.ch/index_EN
Department of Mathematics
 
print
  

Topics in Mathematics of Computer Science

Please note that this page is old.
Check in the VVZ for a current information.


                                         

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:

Problem sheet 1 Solution

Problem sheet 2 Solution
Problem sheet 3 Solution

Problem sheet 4 Solution

Problem sheet 5 Solution

Problem sheet 6 Solution

 

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

© 2016 Mathematics Department | Imprint | Disclaimer | 5 February 2015
top