![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
Although a general dichotomy for exact counting CSP was proved, the complexity for approximation remains wildly open. I will focus on the program to classifying approximability for bounded-degree Boolean #CSP. Dyer, Goldberg, Jalsenius and Richerby gave a beautiful full classification when the maximum degree is six or above, in which no non-trivial approximation result appears. However, for smaller degrees (maximum degree is five or below), interesting tractable (in term of approximation) cases do appear and a complete classification is far from known. In this talk, I will summary the known results in this range and propose a number of interesting open questions.