Seminar: Complexity Theory
Winter term 2017/2018
Content
The topic of complexity theory are the fundamental boundaries of efficient computation. Complexity theory deals with "inherrent difficulties" of algorithmic problems. We do not ask how efficient a certain algorithm solves a problem, but instead how efficiently can this problem be solved in general. Here efficiency is mesured by the amount of resources required, such as computation time, memory or communication bandwidth.
A special difficultiy here is to compare different measures of resources and thus some questions arise like "can every algorithm using few memory be simulated by a time-efficient one?" or "Are randomized algorithms in principle more efficient than deterministic ones?".
Prerequisites
This Seminar is addressed to bachelor as well as master students.
Knowledge of the topics from the basic courses "Data Structures and Algorithms" and "Computability and Complexity" is required for participation. The course "Complexity Theory" might be helpfull, but is not required.
Organization
The seminar-talks will be held in german or english.
Time and Place
This course is a block seminar at the end of the Semester.
Precise dates will be announced later.
Instructors
Requirements
Each participant of the seminar will be assigned a specific topic, usually in form of a research paper or a book chapter. He or she is expected to give a talk of about 45-60 minutes about it and write a paper of about 5 pages summarising it.
The topics will be assigned in the first meeting of the seminar.