Techniques for Counting Problems
Advanced Course, 2+1
Basic Information
Lectures: | Thursdays, 14:00 to 16:00 |
---|---|
Lecturers: | Jacob Focke, Philip Wellnitz |
First lecture: | April 13 |
Tutorials: | TBD |
Assistant: | Philipp Schepper |
First tutorial: | TBD |
Credits: | 5 |
Exam: | TBD |
Prerequisites: | Basic knowledge in Algorithms |
Description
In this course we give an introduction to counting problems and counting complexity. While often in complexity theory we investigate decision problems of the form "Does problem X have a solution?", here we focus on questions of the form "How many solutions does problem X have?". Such questions are motivated for instance by applications in
- statistical physics - "How many different states are there in some system of particles?",
- probability theory - "How many outcomes of a random experiment contributes to some event in comparison to the overall number of possible outcomes?",
- pattern counting - "How frequent is some pattern in a given biological networks/neural networks/the internet/social network...?" ,
- database theory - "How many answers are there to a given query in a given database?",
- ...
We cover selected techniques that have been used to analyze the complexity of counting problems and discuss many of these techniques in the context of counting generalized colorings of graphs, for example:
- "How many 3-colorings are there in a given graph?"
- "How many independent sets are there in a given graph?"
Schedule
Lecture | Lecturer | Topic | Reference (see below) |
---|---|---|---|
April 13 | Jacob Focke | Introduction | |
April 20 | Philip Wellnitz | Counting vs Decision 1 | |
April 27 | JF | Counting vs Decision 2 | |
May 4 | JF | Counting Graph Colorings 1 | |
May 11 | JF | Counting Graph Colorings 2 | |
(May 18) | |||
May 25 | PW | Parameterized Counting 1 | |
June 1 | PW | Parameterized Counting 2 | |
(June 8) | |||
June 15 | PW | Limitations of Counting Dichotomies | |
June 22 | JF | Approximate Counting 1 | |
June 29 | JF | Approximate Counting 2 | |
July 6 | PW | Counting and Sampling 1 | |
(July 13) | |||
July 20 | PW | Counting and Sampling 2 |
Exercise Sets
Exercise Set | Due date | Tutorial Session |
---|
Literature
(Additional literature for specific lectures will be added after the corresponding lectures.)