Se­mi­nar Ad­van­ced Al­go­rithms

Lecturer: Prof. Dr. Christian Scheideler

Module Information:

  • 5 ECTS

First Meeting:

  • To be determined

Topics:

Participants can select one of the following papers (their pdf's can be found in PANDA):

  • Amitabha Bagchi, Ankus Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler. The Effect of Faults on Network Expansion. Theory of Computing Systems 2006.
  • Rene Beier, Berthold Vöcking. Random knapsack in expected polynomial time. JCSS 2004.
  • Andras Benczur and David Karger. Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs. SIAM Journal of Computing 2015.
  • Guy Blelloch, Yan Gu, Julian Shun, Yihan Sun. Parallelism in Randomized Incremental Algorithms. Journal of the ACM 2020.
  • Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Structures and Algorithms 2019.
  • Arut Czumaj and Christian Sohler. Testing Expansion in Bounded-Degree Graphs. Combinatorics, Probability and Computing 2010.
  • Michael Dinitz, Jeremy Fineman, Seth Gilbert, Calvin Newport. Smoothed Analysis of Information Spreading in Dynamic Networks. Journal of the ACM 2024.
  • Mohsen Ghaffari, Krzysztof Nowicki, Mikkel Thorup. Faster Algorithms for Edge Connectivity via Random 2-Out Contractions. SODA 2020.
  • Bernhard Haeupler. Analyzing Network Coding (Gossip) Made Easy. Journal of the ACM 2016.
  • Valerie King, Shay Kutten, Mikkel Thorup. Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication. PODC 2015.
  • Valerie King, Alex Thomo, Quinton Yong. Computing (1+epsilon)-approximate degeneracy in sublinear time. IJCAI 2023.
  • Shen Chen Xu. Exponential Start Time Clustering and its Applications in Spectral Graph Theory. PhD Thesis, CMU, 2017.

Submission of almost final versions of the reports: June 30.

Submission of final versions of reports: Aug 15.

The seminar itself will take place as a block seminar at Sept 23-24. All participants are required to be present at the seminar.

Grading:

Participants are expected to prepare a detailed report (~20 pages) and a presentation of their topic. Both need to be passed in order to pass the seminar, the report counts 60% and the presentation 40% towards the final grade. Please be aware that reports are checked for plagiarism, so use your own words as much as possible and cite anything you take from other sources! If you are not sure about what is considered to be plagiarism, please consult the following leaflet.

Prerequisites:

It is highly recommended that participants of the seminar have a strong algorithms and theory background.

Sie interessieren sich für: