Randomized Algorithms & Probabilistic Methods

Instructors

Prof. Dr. Angelika Steger

Time and Place

First meeting and assignment of talks:

Thursday, February 27th, at 3:15 pm in CAB G 57

Talks:

To be announced.

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 should also be a good starting point for a subsequent (Bachelor/Master) thesis or Semesterarbeit. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA) 2014.

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 point (2KP in this case) is determined by the rules for seminars in D-INFK. Unfortunately, there is no way to treat students from D-MATH differently.

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.

Literature

• Faster Agreement via a Spectral Method for Detecting Malicious Behavior (King and Saia) http://epubs.siam.org/doi/abs/10.1137/1.9781611973402.58
  Supervisor: Johannes Lengler
• Arboricity and spanning-tree packing in random graphs with an application to load balancing (Gao, Pérez- Giménez and Sato) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.23 Supervisor: Rajko Nenadov
• First Come First Served for Online Slot Allocation and Huffman Coding (Khare, Mathieu and Young) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.33 Supervisor: Hafsteinn Einarsson
• Broadcast Throughput in Radio Networks: Routing vs. Network Coding (Alon, Ghaffari, Haeupler and Khabbazian) http://epubs.sia am.org/doi/abs/10.1137/1.9781611973402.132 Supervisor: Felix Weissenberger
• Improved upper bounds for Random-Edge and Random-Jump on abstract cubes (Hansen, Paterson, Zwick) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.65 Supervisor: Ralph Keusch
• MCMC sampling colourings and independent sets of G(n, d/n) near uniqueness threshold (Efthymiou) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.22 Supervisor: Andreas Noever
• Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids (Dietzfelbinger and Woelfel) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.60 Supervisor: Ueli Peter
• Streaming Balanced Graph Partitioning Algorithms for Random Graphs (Stanton) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.95 Supervisor: Nemanja kori
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms (Ma) http://epubs.siam m.org/doi/abs/10.1137/1.9781611973402.85 Supervisor: Frank Mousset
• A constructive algorithm for the Lovasz Local Lemma on permutations (Harris and Srinivasan) http://www.cs.umd.edu/~srin/PDF/2014/lopsided-lll-conf.pdf
  Supervisor: Asaf Ferber

Schedule