Sem­in­ar Ad­vanced Al­gorithms

Lecturer: Prof. Dr. Christian Scheideler

Module Information:

  • 5 ECTS

First Meeting, Selection of Participants, and Topic Assignment:

  • Friday, April 5, at 4 pm in F1.110 (Fürstenallee)

Submission of proposals for topics:

  • Every student interested in participating in the seminar needs to submit a proposal to scheideler@upb.de by the end of Thursday, April 11. The proposal should contain the theory background (courses) of the student as well as at least three papers from the list below that he/she would like to work on.

Submission of almost final versions of the reports: end of June

Submission of final versions of reports: August 11 (this is a firm deadline!)

The seminar itself will take place as a block seminar at September 3-4. All participants are required to be present at the block 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 course, and both count 50% 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!

Topics:

It is highly recommended that participants of the seminar have a strong algorithms and theory background. Please have a look at the papers below, which represent optional topics, in order to check whether you have the necessary background to read them (just google for them).

Parallel and distributed algorithms:

  • Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Oops, an error occurred! Code: 2024122202104486540662. CoRR abs/1810.05303 (2018)
  • Kristian Hinnenthal, Christian Scheideler, and Martihn Struijs. Oops, an error occurred! Code: 2024122202104406318d59. Preprint provided to participants.
  • Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. Oops, an error occurred! Code: 20241222021044ba755b6f Theoretical Computer Science 608: 255-267 (2015).
  • Michael König and Roger Wattenhofer. Oops, an error occurred! Code: 202412220210448dabb23d. OPODIS 2013: 191-205.

Consensus and Blockchains:

  • Rafael Pass and Elaine Shi. Oops, an error occurred! Code: 20241222021044476029d3. CSF 2017: 115-129.
  • T-H. Hubert Chan and Rafael Pass and Elaine Shi. Oops, an error occurred! Code: 20241222021044ef875aaf. Cryptology ePrint Archive: Report 2018/980.
  • Rafael Pass and Elaine Shi. Oops, an error occurred! Code: 2024122202104463f66389 PODC 2017: 315-325.

Social Systems:

  • Rediet Abebe, Jon M. Kleinberg, David C. Parkes, and Charalampos E. Tsourakakis. Oops, an error occurred! Code: 202412220210448b5745aa. KDD 2018: 1089-1098.
  • Flavio Chierichetti and Jon M. Kleinberg. Oops, an error occurred! Code: 2024122202104479da8613 SODA 2012: 1036-1055.
  • Jon M. Kleinberg. Oops, an error occurred! Code: 20241222021044e91b5b67. STOC 2000: 163-170.
  • Baruch Awerbuch and Robert D. Kleinberg. Oops, an error occurred! Code: 2024122202104448b184d9 COLT 2005: 233-248.

Efficient Algorithms:

  • Rene Beier and Berthold Vöcking. Oops, an error occurred! Code: 20241222021044b813cf54. Journal of Computer and Systems Science 69(3): 306-329 (2004).
  • Rold Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. Oops, an error occurred! Code: 20241222021044e331ce08. ESA 2011: 736-747.
  • Artur Czumaj and Christian Sohler. Oops, an error occurred! Code: 202412220210448ae87382. STOC 2004: 175-183.

Coding Algorithms:

  • Bernhard Häupler. Oops, an error occurred! Code: 2024122202104453c53388. STOC 2011: 293-302.
  • Amin Shokrollahi. Oops, an error occurred! Code: 202412220210443c70d203. IEEE Transactions on Information Theory 52(6): 2551-2567 (2006).
  • Martina Eikel and Christian Scheideler. Oops, an error occurred! Code: 20241222021044304e9778. TOPC 2(3): 18:1-18:33 (2015).

Security-related topics:

  • Michael T. Goodrich, Evgenios M. Kornaropoulos, Michael Mitzenmacher, and Roberto Tamassia. Oops, an error occurred! Code: 2024122202104462688c17. EuroS&P 2017: 285-300.
  • Michael T. Goodrich. Oops, an error occurred! Code: 202412220210442baa393a. STOC 2014: 684-693.
  • Aris Anagnostopoulos, Michael T. Goodrich, and Roberto Tamassia. Oops, an error occurred! Code: 20241222021044d5bcd7e6. ISC 2001: 379-393.

 

Further information: