184.687 Seminar in Complexity Theory
This course is in all assigned curricula part of the STEOP.
This course is in at least 1 assigned curriculum part of the STEOP.

2021S, SE, 2.0h, 3.0EC


  • Semester hours: 2.0
  • Credits: 3.0
  • Type: SE Seminar
  • Format: Online

Learning outcomes

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

Subject of course

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.

Teaching methods

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

Mode of examination


Additional information

ECTS Breakdown

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

 75 h = 3 Ects
Please consider the plagiarism guidelines of TU Wien when writing your seminar paper: Directive concerning the handling of plagiarism (PDF)



Course dates

Thu17:00 - 19:0004.03.2021 online via Zoom;: https://tuwien.zoom.us/j/4826230572 (LIVE)first class
Fri09:00 - 11:0016.04.2021 online via Zoom;: https://tuwien.zoom.us/j/4826230572 (LIVE)students' presentations, part 1
Fri09:00 - 11:0028.05.2021 online via Zoom;: https://tuwien.zoom.us/j/4826230572 (LIVE)students' presentations, part 2

Examination modalities

Assessement is based on the oral presentations

Course registration

Begin End Deregistration end
04.03.2021 00:00 08.03.2021 00:00 08.03.2021 00:00


Study CodeObligationSemesterPrecon.Info
066 931 Logic and Computation Mandatory elective


No lecture notes are available.

Previous knowledge

Prerequisite: VU Complexity Theory 181.142


if required in English