---

Theory of Computation
Seminar - Winter Term 2015/16
Fabian Kuhn

 

Seminar Topic

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 on research papers from one more specific area.

2015/16 Topic: Graph/Network Decompositions

For the current seminar, the papers are all about various kinds of network decompositions and their applications. The objective is usually to decompose a given graph into simpler parts with properties that allow to solve some given problem in an efficient manner. Often, graph decompositions are used in the context of networks to tackle various computation or communication tasks. Sometimes, the goal is to decompose the graph into clusters with small diameter such that problems can be dealt with in a more local way by delegating the major part of computations to individual clusters. Sometimes, we want to decompose the graph into simple structers like trees which then for example allow to balance the load of different communication tasks or to solve communication tasks in simpler ways.

Administrative information

In order to get a grade, students have to study and later present the content of a research paper and each student also has to hand in a short written report about the paper (see details below). The seminar will be held as a block seminar on a day towards the end of the semester. In order to pass, attendance to all talks on the seminar day is mandatory. Your slides and talk should be in English. The presentation should last 30 minutes plus about 10 minutes of discussion.

We will meet the first time in the 2nd week of the semester, on Wednesday, October 28, at 12:15. room 106-00-007.

Requirements

The course is mainly directed towards Master students and 3rd year Bachelor 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.

Written Report: You will have to write a report of at least one page. The report should be a critical discussion of the paper. For example: Why is the paper interesting? Do you see any particular strengths or any weaknesses? Can the results be applied in practice or what would one need to change so that the results become practical? Do you see any interesting questions for follow-up research? Do you know any practical or theoretical work that is based on the paper?

In addition, every student who participates in the seminar will be assigned two papers which are presented by other students. You will need to prepare (and hand in before the seminar day) three questions for each of the two papers.

Timeline

We require the following steps to ensure a good quality of the talks and hope that these will result in a good grade for you (all dates are still tentative and might change):

• Until November 13: Decide for a paper.
(please send an email with your preference(s))
• Until December 11: Have a first meeting with your mentor (you need to read the assigned literature and have some idea on how to present it before this meeting).
• Before Christmas: Send an email to your mentor in which you describe you plan to structure your presentation.
• At least 1 week before your talk: Discuss your (complete) slides with your mentor, so that he/she can give feedback.
• One day before the presentation date: Hand in your report, an electronic copy of your slides, and the question on the two assigned papers.
• Friday, January 29, 2016: Presentation

Assigned Papers

1. Network Decomposition and Locality in Distributed Computation - Awerbuch, Luby, Goldberg, Plotkin (Student: Uwe Waldvogel, Contact person: Yannic Maus)
   This paper introduces a distributed method to efficiently partition the sets of nodes of a given graph into clusters with the following properties
   • Each cluster has low diameter
   • The clustergraph can be partitioned into few independent sets (there is no connection between two clusters which belong to the same independent set)
   Many (distributed) problems can be solved fast given a graph with small diameter; therefore they can be solved quickly on the clusters. The second property helps in dividing a big problem into small problems which then can be handled at the same time.
2. Low diameter graph decompositions - Linial, Saks (Student: Li Kecen, Contact person: Yannic Maus)
   Linial and Saks improve the network decomposition of Awerbuch, Luby, Goldberg and Plotkin with the help of randomization (and also for the non-distributed scenario). They also show that there are graphs which cannot be decomposed in a better way.
3. A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics - Fakcharoenphol, Rao, Talwar (Student: Christof Schötz, Contact person: Hamid Ghods)
   The paper shows how to hierarchically decompose a graph (or more generally a metric) into clusters such that the resulting (virtual) tree has at most logarithmic average stretch. In fact, it is even shown that for every pair of nodes, the expected distance in the tree is at most O(log n) times the actual distance of the two nodes.
4. A Graph-Theoretic Game and Its Application to the k-Server Problem - Alon, Karp, Peleg, West (Student: Ganindu Prabhashana, Contact person: Mohamad Ahmadi)
   The paper shows how graph decompositions can be used to compute a spanning tree with good average stretch (a spanning tree which approximates distances well on average).
5. Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and Low-Stretch Subgraphs - Blelloch, Gupta, Koutis, Miller, Peng, Tangwongsan (Student: Ngoc Hanh Phan, Contact person: Anisur R. Molla)
   The paper in particular presents a parallel algorithm to efficiently compute a decomposition with similar (but in some sense better) properties as the ones of the first three papers. As a first application, the decomposition is used to get a parallel version of the low average stretch spanning tree algorithm of the previous paper. The algorithms of this paper also directly work in a distributed model where each message is bounded in size.
6. Exact Combinatorial Branch-and-Bound for Graph Bisection - D. Delling, A. V. Goldberg et al. (Student: Kemal Cagin Gülsen, Contact person: Oleksii Saukh)
   Minimum graph bisection problem is defined as follows: a graph is partitioned into two equally-sized cells while minimizing the number of edges between them. They devise an algorithm that is based on the branch-and-bound framework. They derive the bounds by computing minimum s-t cuts between partial assignments (A,B), i. e., A and B are subsets of V such that they do not share any node.
7. Scalable K-Means++ - B. Bahmani, B. Moseley, A. Vattani, R. Kumar, S. Vassilvitskii (Student: Stefan Berea, Contact person: Mohamad Ahmadi)
   k-means has been always a popular clustering algorithm. However, a proper initialization for this algorithm is crucial to its performance. In this paper the authors introduce a new algorithm to obtain a good initial set of centers while the necessary number of passes over the data is drastically smaller than other existing solutions.