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
Last Updated: 2026-02-05 14:59:47
Abstract
Part 1: Application of Fourier analysis in combinatorics (influence of variables on Boolean functions, KKL and Friefgut's theorems for Juntas, Gaber-Galil expanders with application to non-approximability of Maxclique).Part 2: Application of permutation groups (Luks theorem on graph-isomorphism).
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 graph theory, complexity theory and in particular, in the analysis of Boolean functions. No prerequisite, the relevant background will be introduced as necessary.
Content
Time permitting, the following topics should be discussed: Construction of expanding graphs. Non-approximability of the Maxclique problem. Linearity test. Influence of variables on Boolean functions (Dictatorships and Juntas ...).
General Information
- Language
- English
- 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 |
|
2 h weekly |
| exercise | Topics in Mathematics of Computer Science |
|
1 h weekly |