D1
Algorithms & Complexity

Techniques for Counting Problems

Advanced Course, 2+1

Basic Information

Lectures:Thursdays, 14:00 to 16:00
Lecturers:Jacob FockePhilip 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

LectureLecturerTopicReference (see below)
April 13Jacob FockeIntroduction 
April 20Philip WellnitzCounting vs Decision 1 
April 27JFCounting vs Decision 2 
May 4JFCounting Graph Colorings 1 
May 11JFCounting Graph Colorings 2 
(May 18)   
May 25PWParameterized Counting 1 
June 1PWParameterized Counting 2 
(June 8)   
June 15PWLimitations of Counting Dichotomies 
June 22JFApproximate Counting 1 
June 29JFApproximate Counting 2 
July 6PWCounting and Sampling 1 
(July 13)   
July 20PWCounting and Sampling 2 

Exercise Sets

Exercise SetDue dateTutorial Session

Literature

(Additional literature for specific lectures will be added after the corresponding lectures.)