Limits and applications of group algebras for parameterized problems

The fastest known randomized algorithms for several parameterized problems use reductions to the k-MLD problem: detection of multilinear monomials of degree k in polynomials presented as circuits. The fastest known algorithm for k-MLD is based on 2^k evaluations of the circuit over a suitable algebra. We use communication complexity to show that it is essentially optimal within this evaluation framework. On the positive side, we give additional applications of the method: finding a copy of a given tree on k nodes, a minimum set of nodes that dominate at least t nodes, and an m-dimensional k-matching. In each case, we achieve a faster algorithm than what was known before. We also apply the algebraic method to problems in exact counting. Among other results, we show that a variation of it can break the trivial upper bounds for the disjoint summation problem.