Abstract

For exact counting in #CSP over Boolean variables, all problems are classified into 3 types: (1) P-time computable; or (2) #P-hard in general but P-time computable over planar structures; or (3) #P-hard even for planar structures.  Moreover, type (2) corresponds to those problems which can be solved by Valiant's holographic algorithms with matchgates. For Holant problems there is a new tractable class of problems hidden from the days of FKT. This third and final session will discuss these topics.

The first session of this mini course will take place on Monday, January 25 from 9:30 am – 10:30 am; the second session of this mini course will take place on Wednesday, January 27 from 11:00 am – 12:00 pm.

Video Recording