After successful completion of the course, students are able to

• to name advanced topics of complexity theory
• to reproduce foundational research results on Problems beyond the classical complexity theory of decision problems
• to overlook the relevant literature for counting and enumeration problems
• to analyse the complexity of counting and enumeration problems

Usually, when detailed complexity analyses are carried out, we mean the complexity of decision problems. Here we have the most mature complexity theory at our disposal for the analysis and complexity classification of problems. However, in many applications, counting problems and enumeration problems are possibly yet more important than decision problems. For instance, in the database area, when evaluating queries, we are usually interested in the output of all answers rather than in the question, if at least one answer  exists.

Students have to prepare oral presentations of selected research articles on topics treated in this seminar

ECTS Breakdown

 65 h Providing short sumaries and presentations
 10 h Presence in class
 
----------------------------------------------------------------

 75 h = 3 Ects

Organisation

It is planned to have the students' presentations "live" in the seminar room. If the Covid situation requires, these classes will switch to online via Zoom. The dates as announced in the first class are firm independently of the Covid situation.

Assessement is based on the oral presentations

Prerequisite: VU Complexity Theory 181.142