BARC/EADS Talk by Radu Curticapean

Title

Counting complexity: Perfect matchings and small patterns

Abstract

This talk addresses counting problems. In such problems, we do not only want to know whether a problem instance admits a solution, but we are rather interested in the number of such solutions. The complexity-theoretic study of such problems was kicked off by Valiant's 1979 hardness proof for the permanent, which showed that counting perfect matchings is at least NP-hard (whereas finding a perfect matching is well-known to be polynomial-time solvable.) During this talk, Radu will survey what is known about his two favorite questions in counting complexity:

1. What kind of graph structure makes counting perfect matchings tractable? For instance, there are some classical, surprising, and beautiful results showing that the problem is polynomial-time on planar graphs. But how far can this be generalized, say, to graphs excluding fixed minors?

2. A differently flavored problem is that of counting small patterns (motifs) in large graphs: Here you're given a pattern H on k vertices, where k is considered small, and a large host graph G on n vertices. Now count all subgraphs of G that are isomorphic to H. This problem can always be solved in time O(n^k) by brute-force, but many classes of patterns admit exponents that are significantly lower than k. We're going to close in on the true exponents with upper and lower bounds.

Bio

Radu received his PhD in 2015 from Saarland University, Germany, and has since been a postdoc at the Hungarian Academy of Sciences in Budapest, interrupted by a two-semester fellowship at the Simons Institute for the Theory of Computing in Berkeley. Radu’s main research area is counting complexity, and his interests include parameterized and fine-grained complexity theory, graph minor theory and, somewhat recently, the theory of graph limits. As of March 1, 2018 Radu joined BARC as a postdoctoral researcher.