VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Topics in Mathematics of Computer Science: Expander Graphs
Last Updated: 2026-02-05 15:13:59
Abstract
In a first part we present both constructions and applications of expander graphs. These are graphs with few edges, but nevertheless very well connected. Said differently, all subsets of nodes have "many" neighbours, a property that is related to the eigenvalues of the adjacency matrix of the graph.
Objective
A first goal of the lecture is to sensibilize students in Mathematics to some settings typical from Theoretical Computer Science. A second goal is to illustrate how tools from classical Mathematics (linear algebra, Fourier analysis, ...) have been applied to deal with some problems in both graph theory and omplexity theory .
Content
The lecture will discuss both constructions and applications of expander graphs. These are graphs with few edges, but nevertheless very well connected. Said differently, all subsets of nodes have "many" neighbours, a property that is related to the eigenvalues of the adjacency matrix of the graph.
General Information
- Language
- English
- Levels
- BSC , MSC
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 20 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Topics in Mathematics of Computer Science: Expander Graphs |
|
2 h weekly |
| exercise | Topics in Mathematics of Computer Science: Expander Graphs |
|
1 h weekly |