The spring semester 2021 will certainly take place online until Easter. Exceptions: Courses that can only be carried out with on-site presence. Please note the information provided by the lecturers.

401-3057-61L  Expander Graphs and Their Applications

SemesterSpring Semester 2016
LecturersE. Kowalski
Periodicitynon-recurring course
Language of instructionEnglish


AbstractThe course will present the basic theory and selected applications of expander graphs. It will develop the general idea of expansion of graphs and the different formulations of expanding graphs. The existence of expanding graphs will then be established using both probabilistic and deterministic methods. Applications to number theory, geometry and theoretical computer science will be described.
Objective
ContentThe course will present the basic theory and selected applications of expander graphs. It will first develop the general idea of expansion of graphs and the different formulations of expanding graphs. The existence of expanding graphs will then be established using both probabilistic and deterministic methods (including a discussion of the recent work on expansion of finite linear groups). Applications to number theory, geometry and theoretical computer science will be described.
Lecture notesLecture notes will be available.
LiteratureHoory, Linial and Wigderson: Expander graphs and their applications,
Bull. Amer. Math. Soc. 43 (2006), 439-561
Prerequisites / NoticePrerequisites: Measure and integration, algebra I + II.