Department of Computer Science | Institute of Theoretical Computer Science
18 Feb 15:15, CAB G15.2
Tuesday, 24 March 15:15 - 18:00, HG F 26.5
Monday, 30 March 15:15 - 18:00, LFW B 2
Tuesday, 31 March 15:15 - 18:00, HG F 26.5
Wednesday, 01 April 15:15 - 18:00, IFW C 33
The seminar takes place each spring semester. The aim is to study papers which bring the students to the forefront of today's research topics. It is as well a good starting point for a subsequent (Bachelor/Master) thesis or semester project. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA) 2020.
The seminar is open for both students from mathematics and students from computer science. As prerequisite we require that you passed the course Randomized Algorithms and Probabilistic Methods (or equivalent, if you come from abroad. In this case please send an e-mail to the lecturer to check if you have the required background).
Please note: according to ETH rules all students of this seminar will receive the same number of credit points, regardless of their home department. The number of credit points (2CP in this case) is determined by the rules for seminars in D-INFK.
Giving a preparatory talk (at least) a week before your actual talk is mandatory (as explained in the first meeting of the seminar). Failing to do one will result in failing the seminar. For details on how to prepare your talk please read the guidelines given here. We also compiled a list of things you should look out for here. Due to the high number of enrolled students, we might assign up to two students per paper. Please note in additional that if there are two students assigned to the paper they should split the talk between them and they should switch roles between rehearsal talk and final talk.
Date | Time | Paper | Student | Advisor |
24 Mar | 15:15 | Acyclic subgraphs of tournaments with high chromatic number | Daniel, Domagoj | Miloš Trujić |
24 Mar | 16:15 | An Optimal Decentralized (Δ+1)-Coloring Algorithm | Ben, Joël | Angelika Steger |
30 Mar | 15:15 | Testing Linear Inequalities of Subgraph Statistics | Katja, Lukas V. | Frederik Benzing |
30 Mar | 16:15 | The Random-Query Model and the Memory-Bounded Coupon Collector | François, Niko | Xun Zou |
30 Mar | 17:15 | The probability of selecting k edge-disjoint Hamilton cycles in the complete graph | Emanuel, Patrick | Charlotte Knierim |
31 Mar | 15:15 | Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game | Giulia, Lorenzo | Pascal Su |
31 Mar | 16:15 | Approximate Maximum Matching in Random Streams | Anastasia, Jeff | Asier Mujika |
01 Apr | 15:15 | A randomly weighted minimum spanning tree with a random cost constraint | Ning, Yiting | Maxime Larcher |
01 Apr | 16:15 | Choice and Bias in Random Walks | Marcel, Lukas L. | Kalina Petrova |