Theory of Computation
Seminar - Winter Term 2012/13
Fabian Kuhn

 

General Description

The main objective of the theory of computation seminar is to provide an opportunity to learn about some of the exciting topics current theoretical computer science research has to offer. We plan to organize the seminar every winter term. Each time, the seminar will be about one general theme. Throughout the semester, we will together go through papers or other material covering interesting aspects of the general topic. We hope to have informal meetings with lively discussions. In order to get a grade for the seminar, students are expected to actively participate in the seminar, to present some part of the material, and to lead the discussion about that part.

2012/13 Topic: Spectral Graph Theory

The topic of this year's seminar will be spectral graph theory. Interestingly, the spectral properties (i.e., the eigenvalues and eigenvectors) of the adjacency or related matrices of a graph can tell us a lot about the properties of the graph. The goal will be to discover some of these connections between linear algebra and graph theory and and also some algorithmic consequences. As the main resource for the seminar material, we will use the excellent lecture notes on the topic by Dan Spielman from Yale University.

Seminar Hours

We will (tentatively) meet each

• Thursday 12:15-14:00, room 106-00-015

The first seminar will be on Thursday, November 8. To have a common idea of the general topic of the seminar, please read the introductory chapter of the lecture notes mentioned above before coming to the first meeting. We will use the first meeting to discuss some material from the second chapter and to plan the rest of the semester.

Requirements

The course is mainly directed towards Master students (and interested PhD students) of computer science or mathematics. Some knowledge of graph theory and linear algebra is expected.