Spring 2016

Dichotomy for Real Holant^c Problems

Wednesday, Jun. 7, 2017 9:30 am10:30 am

Add to Calendar

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks. Counting CSP is a special case. Therefore a classification for Holant problems is more difficult to prove. This is so not only because it implies a classification for counting CSP, and the deeper reason is the existence of  more intricate polynomial time tractable problems.
We discover a new family of constraint functions which define polynomial time computable counting problems. These constraints do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We show that this new family supplies the last piece of tractability and its discovery enables us to prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0-1 pinning functions. Previously, dichotomy for  the same framework was only  known for symmetric constraint functions.  We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.
PDF icon Dichotomy for Real Holant^c Problems850.2 KB