Spring 2016

Counting Approximation Complexity Classification Through Clones and Invariants

Thursday, March 31st, 2016 9:30 am10:15 am

Add to Calendar

The complexity landscape of approximate computing partition functions appears to be quite complicated. This makes the problem of classifying such problems according to their approximation complexity very difficult. We try to separate counting problems with respect to gadget reductions, which is equivalent to the study of clones related to the problem, that is, sets of functions or relations closed under gadgets. We survey the several main approaches to such classification, as well as some new and existing results.