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

Properties

  • Semester hours: 2.0
  • Credits: 3.0
  • Type: SE Seminar
  • Format: Distance Learning

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

Immanent

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)

Lecturers

Institute

Course dates

DayTimeDateLocationDescription
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

Curricula

Study CodeSemesterPrecon.Info
066 931 Logic and Computation

Literature

No lecture notes are available.

Previous knowledge

Prerequisite: VU Complexity Theory 181.142

Language

if required in English