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. Parallelism in Randomized Incremental Algorithms. CoRR abs/1810.05303 (2018)
  • Kristian Hinnenthal, Christian Scheideler, and Martihn Struijs. Fast Distributed Algorithms for LP-type Problems of Bounded Dimension. Preprint provided to participants.
  • Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How many ants does it take to find the food? Theoretical Computer Science 608: 255-267 (2015).
  • Michael König and Roger Wattenhofer. On Local Fixing. OPODIS 2013: 191-205.

Consensus and Blockchains:

  • Rafael Pass and Elaine Shi. Rethinking Large-Scale Consensus. CSF 2017: 115-129.
  • T-H. Hubert Chan and Rafael Pass and Elaine Shi. PiLi: An Extremely Simple Synchronous Blockchain. Cryptology ePrint Archive: Report 2018/980.
  • Rafael Pass and Elaine Shi. FruitChains: A Fair Blockchain. PODC 2017: 315-325.

Social Systems:

  • Rediet Abebe, Jon M. Kleinberg, David C. Parkes, and Charalampos E. Tsourakakis. Opinion Dynamics with Varying Susceptibility to Persuasion. KDD 2018: 1089-1098.
  • Flavio Chierichetti and Jon M. Kleinberg. Voting with limited information and many alternatives. SODA 2012: 1036-1055.
  • Jon M. Kleinberg. The small-world phenomenon: an algorithmic perspective. STOC 2000: 163-170.
  • Baruch Awerbuch and Robert D. Kleinberg. Competitive Collaborative Learning. COLT 2005: 233-248.

Efficient Algorithms:

  • Rene Beier and Berthold Vöcking. Random knapsack in expected polynomial time. Journal of Computer and Systems Science 69(3): 306-329 (2004).
  • Rold Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. Tolerant Algorithms. ESA 2011: 736-747.
  • Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear-time. STOC 2004: 175-183.

Coding Algorithms:

  • Bernhard Häupler. Analyzing network coding gossip made easy. STOC 2011: 293-302.
  • Amin Shokrollahi. Raptor codes. IEEE Transactions on Information Theory 52(6): 2551-2567 (2006).
  • Martina Eikel and Christian Scheideler. IRIS: a robust information system against insider DoS attacks. TOPC 2(3): 18:1-18:33 (2015).

Security-related topics:

  • Michael T. Goodrich, Evgenios M. Kornaropoulos, Michael Mitzenmacher, and Roberto Tamassia. Auditable Data Structures. EuroS&P 2017: 285-300.
  • Michael T. Goodrich. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time. STOC 2014: 684-693.
  • Aris Anagnostopoulos, Michael T. Goodrich, and Roberto Tamassia. Persistent Authenticated Dictionaries and Their Applications. ISC 2001: 379-393.

 

Further information: