Theory of Computation
Seminar - Winter Term 2013/14
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.
2013/14 Topic: Metric Embeddings
Many computational problems involving distances (such as, e.g., the traveling salesperson problem) become easier when the distances form a metric space. That is, when the distances are symmetric and they satisfy the triangle inequality. In addition, often, problems involving metric spaces become easier to solve if the metric space has some nice properties (e.g., Euclidean geometric distances or distances defined by trees). In this years seminar, we will look at important techniques and results on how to approximate distances by simpler metric spaces and on applications of these techniques.
In order to get a grade (and credit points), attendance to all seminars is mandatory and each student will have to present one topic and lead the discussion on that topic. In addition, it is expected that students actively participate in discussions. For an overview of possible topics, you may consider the following existing lectures on metric embedding.
Seminar Hours
We will meet each
- Tuesday 13:15-15:00, room 106-00-015
- First seminar: Tuesday Oct 29
Requirements
The course is mainly directed towards Master students (and interested PhD students) of computer science or mathematics. There are no specific requirements, but students should be interested in mathematical and algorithmic questions and basic mathematical maturity is expected.