Fall 2014

A Survey of Counting Dichotomies and Holographic Algorithms

Wednesday, September 17th, 2014 10:20 am11:10 am

Add to Calendar


Calvin Lab Auditorium

I will describe a number of recent dichotomy theorems in counting complexity. These include dichotomies for graph homomorphisms (spin systems), for constraint satisfactions, and for holant problems. I will describe the role holographic reductions play both in holographic algorithms and holographic reductions for hardness. I will present the thesis that for a very wide class of counting problems expressible as a sum-of-product computation (also known as partition functions), the entire class is divided into exactly three categories: (A) those that are solvable in polynomial time (B) those that are solvable in polynomial time for planar structures, but #P-hard in general, and (C) those that remain #P-hard even for planar structures. Furthermore, type (B) problems are solvable in P for planar structures precisely by Valiant's holographic algorithm based on matchgates, followed by Kasteleyn's algorithm for perfect matchings, making this a universal algorithm for this type of problems. This thesis is only partially proved (for symmetric constraint functions on Boolean variables, and for some asymmetric constraint functions.)