Limits and applications of group algebras for parameterized problems
April 8, 2009
Several combinatorial problems in parameterized complexity reduce to the problem of detecting degree-$k$ square-free monomials in polynomials presented as circuits. The best known (randomized) algorithm for this problem requires only $O^*(2^k)$ time and oracle access to an arithmetic circuit, i.e. the ability to evaluate the circuit on (randomly chosen) points from a group algebra. This algorithm can be used to obtain the best known algorithms for several parameterized problems. In this work we show that the $O^*(2^k)$ algorithm is essentially optimal within this evaluation-oracle framework. On the positive side, we apply the algebraic method to problems in exact counting. Among other results, we show that a combination of dynamic programming and a variation of the algebraic method can break the trivial dynamic programming upper bounds for exact parameterized counting in fairly general settings.

This is joint work with Ryan Williams, to appear in ICALP 2009.