RA&PM Seminar

Randomized Algorithms & Probabilistic Methods

Instructor:

Prof. Dr. Angelika Steger

First meeting and assignment of talks:

Tuesday, February 28th, at 3:15 pm in CAB G 15.2

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) 2017 and of the conference Meeting on Analytic Algorithmics and Combinatorics (ANALCO) 2017.

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

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:

A preparatory talk (as explained in the first meeting of the seminar) is mandatory. Failing to do one will result in failing the seminar.

Schedule:

The talks will be presented in CAB G 15.2.

Date	Time	Paper	Student	Advisor
04/04	15:15	Random Walks with the Minimum Degree Local Rule Have O(N^2) Cover Time	Martin Raszyk	Pascal Pfister
04/04	16:15	Distributed Degree Splitting, Edge Coloring, and Orientations	Dorela Kozmai	Milos Trujic
04/04	17:15	Random Walks and Evolving Sets: Faster Convergences and Limitations	Samuel Siebenmann	Pascal Su
11/04	15:15	Random Contractions and Sampling for Hypergraph and Hedge Connectivity	Lukas Gianinazzi	Nemanja Skoric
11/04	16:15	Fully Dynamic Connectivity in O(log n(log log n)^2) Amortized Expected Time	Daniel Keller	Ralph Keusch
11/04	17:15	Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search	Pragnya Alatur	Felix Weissenberger
25/04	15:15	A Hybrid Sampling Scheme for Triangle Counting	Stephan Ammann	Florian Meier
25/04	16:15	LSH Forest: Practical Algorithms Made Theoretical	Seyedrouzbeh Hasheminezhad	Frank Mousset
25/04	17:15	On the insertion time of random walk cuckoo hashing	Nicolas Kirchmayr	Hafsteinn Einarsson