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, Feb 28th, 16:15, CAB G56

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

Participants:

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

DateRoomTimePaperStudentAdvisor
20.04.2023CAB H 5213:00 Short Synchronizing Words for Random Automata Morawski Patryk & Nogler Jakob Anders Martinsson
20.04.2023CAB H 5214:00 Player-optimal Stable Regret for Bandit Learning in Matching Markets Chen Daoyuan & Chen Zhiyi Ulysse Schaller
20.04.2023CAB H 5215:00 Bidder Subset Selection Problem in Auction Design Baharav Carmel & Jensen Nils Alexander Meulemans
21.04.2023CAB H 5214:00 Secretary Problems: The Power of a Single Sample Lakis Konstantinos & Vári-Kakas Andor Maxime Larcher
21.04.2023CAB H 5215:00 Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring Ge Chio & Li Jie-Ming Micha Christoph
28.04.2023CAB H 5313:00 Discrepancy Minimization via Regularization Erdmann Christoph & Ravi Raghu Raman Raphael Steiner
28.04.2023CAB H 5314:00 Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching Dufay Marc & Lepel Olivier Yassir Akram
28.04.2023CAB H 5315:00 Spencer's theorem in nearly input-sparsity time Bernold Nicola & Widmer Leo Raphael Steiner
28.04.2023CAB H 5316:00 Online Min-Max Paging Sun Yucheng Maxime Larcher