Limits and applications of group algebras for parameterized problems

Ioannis Koutis, Ryan Williams

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

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 2k 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.

Original languageEnglish (US)
Article number31
JournalACM Transactions on Algorithms
Volume12
Issue number3
DOIs
StatePublished - May 2016
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Algebraic algorithms
  • Color coding
  • Exact counting
  • Multilinear detection
  • Permanent

Fingerprint

Dive into the research topics of 'Limits and applications of group algebras for parameterized problems'. Together they form a unique fingerprint.

Cite this