(Pro-)Se­mi­nar Al­go­rith­men und Kom­ple­xi­tät

We discuss original results from complexity theory and algorithmic results. A detailed list of topics can be found at the bottom of this page and will be presented at the initial meeting.

This seminar can also be credited as proseminar in the Bachelor's course program.  

The seminar will be held as a block seminar.

In­iti­al Mee­ting

  • date: 20.04.2016 - 16:00
  • room: F2.425
  • participation at the initial meeting is mandatory for this seminar

Block Se­mi­nar Dates

Exemplary Talk: 23.06.2016, 18:00, F2.211

Seminar: 14.07.2016, 16:00 (2 talks), 15.07.2016, 14:00 (2 talks), F2.211

List of Talks

Label Cover and the Unique Games ConjectureJohannes Blömer--23.06., 18:00
Sind 12345 und 76438 zufällige Zahlen?1Simon PukropSascha Brauer14.07., 16:00
Zero-knowledge interactive proof for Graph Isomorphisms3Viktor SchellenbergJan Bobolz14.07., 17:00
Approximation of Hierarchical Diameter Clustering4Nils WeidmannKathrin Bujna15.07., 14:00
Unique Games and Inapproximability of Vertex Cover5Marcus HüweJohannes Blömer15.07., 15:00

1: T. M. Cover, J. A. Thomas, Elements of Information Theory, Kapitel 7.
3: O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM (JACM) 38.3 (1991): 690-728.
4: S. Dasgupta, P. Long: Performance Guarantees for Hierarchical Clustering. Journal of Computer and System Sciences, 2005.
5: S. Khot, O. Regev. Vertex cover might be hard to approximate to within 2-eps. Journal of Computer and System Sciences, 74.3, May 2008, 335-349

Ru­les of the game


  • approx. 45 minutes presentation (beamer and slides; whiteboard optional)
  • afterwards discussion
  • we recommend the LaTeX beamer class for your slides (optional)
  • if you do not bring your own laptop (notebook) pc, please inform your advisor


  • length: approx. 8--10 pages at Proseminar and approx. 10--12 pages at Seminar
  • style: according to the standards of a scientific paper
  • typesetting: LaTeX (mandatory)
  • submission: as pdf email attachment to your advisor


The following deadlines are strict. Please be aware that if you do not comply with these deadlines this may result in a fail (i.e., 5,0) in this course.

We request that you meet with your advisor at least four times as specified below. However, contact to your advisor is not limited to these meetings and you may contact your advisor any time between these deadlines if necessary.

  • in the middle of June, at the latest
    • At this point of time, we assume that you have read the literature and that you are able to discuss the details of your topic.
    • Goal: Coordination of the topic between yourself and your advisor.
  • (4 weeks before talk) at the latest
    • You present to your advisor a detailed structuring of your essay.
  • (2 weeks before talk) at the latest
    • Submission of the essay (as pdf or ps via email). Within a week, we will review and annotate your submitted essay.
    • You present to your advisor a detailed concept/structuring of your presentation.
  • (1 week before talk) at the latest
    • You present to your advisor an almost finished set of slides.
    • We will return to you your reviewed and annotated essay.
  • (3 weeks after talk) at the latest
    • Final submission of your essay. This is the version of the essay that will be graded.