# Techniques for Counting Problems

## Basic Information

Lectures: Thursdays, 14:00 to 16:00, E1 4, Room 0.24 Jacob Focke, Philip Wellnitz April 13 Tuesday, 16:00 to 18:00, every other week, E1 4, Room 0.24 Philipp Schepper May 2nd 5 Tuesday, August 08, 10:00, E1.4 Room 0.24 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

LectureLecturerTopicReference (see below)
April 13Jacob FockeIntroduction
Course Overview, Motivation, Basic Definitions
[slides from the motivation]
April 20Philip WellnitzCounting vs Decision 1:
Permanents, Bipartite Matchings, Directed Cycle Covers
[Val79] [BH93]
April 27JFCounting vs Decision 2[Mik19]
May 4JFCounting Graph Colorings 1[CCD19]
May 11 (room change)JFCounting Graph Colorings 2[CCD19] Changed room: E1.4 0.21
(May 18)
May 25PWParameterized Counting 1
June 1 → June 6PWParameterized Counting 2Moved to tutorial slot (4pm-6pm) on June 6
(June 8)
June 15 → June 13PWLimitations of Counting Dichotomies[slides]
Moved to tutorial slot (4pm-6pm) on June 13
June 22  No lecture, instead of July 13
June 29 → July 4JFApproximate CountingMoved to tutorial slot (4pm-6pm) on July 4
July 6PWCounting and Sampling
July 13 (new)  No lecture
July 20  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 SetDue dateTutorial Session
Exercise Set 1April 27May 2
Exercise Set 2May 11May 16
Exercise Set 3May 25May 30
Exercise Set 4June 18June 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.