Techniques for Counting Problems
Advanced Course, 2+1
Basic Information
| Lectures: | Thursdays, 14:00 to 16:00, E1 4, Room 0.24 |
|---|---|
| Lecturers: | Jacob Focke, Philip Wellnitz |
| First lecture: | April 13 |
| Tutorials: | Tuesday, 16:00 to 18:00, every other week, E1 4, Room 0.24 |
| Assistant: | Philipp Schepper |
| First tutorial: | May 2nd |
| Credits: | 5 |
| Exam: | Tuesday, August 08, 10:00, E1.4 Room 0.24 |
| 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 Course Overview, Motivation, Basic Definitions | [slides from the motivation] |
| April 20 | Philip Wellnitz | Counting vs Decision 1: Permanents, Bipartite Matchings, Directed Cycle Covers | [Val79] [BH93] |
| April 27 | JF | Counting vs Decision 2 | [Mik19] |
| May 4 | JF | Counting Graph Colorings 1 | [CCD19] |
| May 11 (room change) | JF | Counting Graph Colorings 2 | [CCD19] Changed room: E1.4 0.21 |
| (May 18) | |||
| May 25 | PW | Parameterized Counting 1 | |
| PW | Parameterized Counting 2 | Moved to tutorial slot (4pm-6pm) on June 6 | |
| (June 8) | |||
| PW | Limitations of Counting Dichotomies | [slides] Moved to tutorial slot (4pm-6pm) on June 13 | |
| No lecture, instead of July 13 | |||
| JF | Approximate Counting | Moved to tutorial slot (4pm-6pm) on July 4 | |
| July 6 | PW | Counting and Sampling | |
| No lecture | |||
| No lecture |
Exercise Sets
Exercise Sheet 4 was the last exercise sheet. You are admitted to the exam if you obtained at least 150 points in total on the exercise sheets. Feel free to contact the lecurers if you are unsure about your exam admittance.
| Exercise Set | Due date | Tutorial Session |
|---|---|---|
| Exercise Set 1 | April 27 | May 2 |
| Exercise Set 2 | May 11 | May 16 |
| Exercise Set 3 | May 25 | May 30 |
| Exercise Set 4 | June 18 | June 20 |
Literature
- [Val79] Leslie G. Valiant. The Complexity of Computing the Permanent; Theor. Comput. Sci. (1979).
- [BH93] Amir Ben-Dor and Shai Halevi. Zero-One Permanent is #P-Complete, A Simpler Proof; ISTCS 1993.
- [Mik19] Istvan Miklos. Computational Complexity of Counting and Sampling (Discrete Mathematics and Its Applications). CRC Press 2019
- [CCD19] Hubie Chen, Radu Curticapean, and Holger Dell. The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms; WG 2019.