(Pro-)Seminar Algorithmen und Komplexitä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.
Initial Meeting
- date: 20.04.2016 - 16:00
- room: F2.425
- participation at the initial meeting is mandatory for this seminar
Block Seminar 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
| Topic | Speaker | Advisor | Date |
|---|---|---|---|
| Label Cover and the Unique Games Conjecture | Johannes Blömer | -- | 23.06., 18:00 |
| Sind 12345 und 76438 zufällige Zahlen?1 | Simon Pukrop | Sascha Brauer | 14.07., 16:00 |
| Zero-knowledge interactive proof for Graph Isomorphisms3 | Viktor Schellenberg | Jan Bobolz | 14.07., 17:00 |
| Approximation of Hierarchical Diameter Clustering4 | Nils Weidmann | Kathrin Bujna | 15.07., 14:00 |
| Unique Games and Inapproximability of Vertex Cover5 | Marcus Hüwe | Johannes Blömer | 15.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
Rules of the game
Presentation
- 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
Essay
- 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)
- example document [pdf]
- example tex sources [tex]
- wikibook on LaTeX
- submission: as pdf email attachment to your advisor
Deadlines
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.