Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Randomized Algorithms & Probabilistic Methods Seminar

Instructor:

Prof. Dr. Angelika Steger

First meeting and assignment of talks:

Tuesday, March 1st, 16:15, CAB G56

Dates and location of the talks:

TBA

Topics:

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) 2022.

Participants:

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.

Important note:

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.

List of Papers (to be extended)

DateRoomTimePaperStudentAdvisor
Tue March 29thCAB G5616:15 Competitive Strategies for Symmetric Rendezvous on the Line Jiahao Qu & Andrzej Turko Ulysse Schaller
Tue March 29thCAB G5617:15 A Note on the width of Sparse Random Graphs Micha Christoph & Michele Meziu Miloš Trujić
Tue March 29thCAB G5618:15 Deterministic algorithms for the Lovasz Local Lemma: simpler, more general,and more parallel Jonas Hübotter & Duri Janett Yassir Akram
Mon April 4thCAB G528:15 New Diameter-Reducing Shortcuts and Directed Hopsets:Breaking theO(√n) Barrier Levan Varamashvili & Antoine Renaud-Goud Kalina Petrova
Mon April 4thCAB G529:15 A Tail Estimate with Exponential Decay for the RandomizedIncremental Construction of Search Structures Daniel Zhang & Yanheng Wang Marc Kaufmann
Tue April 5th CAB G5616:15 A Lower Bound for the n-queens Problems Martin Kucera & Georgy Mitenkov Robert Meier
Tue April 5thCAB G5617:15 Counting Homomorphic Cycles in Degenerate Graphs Zhihan Jin & Aurelio Sulser Miloš Trujić
Tue April 5thCAB G5618:15 Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams Manuel Göggel & Antti Röyskö Maxime Larcher