Spring 2016

The Complexity of Approximating Small Degree Boolean #CSP

Wednesday, March 30th, 2016 2:00 pm2:45 pm

Add to Calendar

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.