Waring Rank, Parameterized and Exact Algorithms
Author:
Preprint
Abstract
Given nonnegative integers $n$ and $d$, where $n \gg d$, what is the minimum number $r$ such that there exist linear forms $\ell_1, \ldots, \ell_r \in \mathbb{C}[x_1, \ldots, x_n]$ so that $\ell_1^d + \cdots + \ell_r^d$ is supported exactly on the set of all degree-$d$ multilinear monomials in $x_1, \ldots, x_n$? We show that this and related questions have surprising and intimate connections to the areas of parameterized and exact algorithms, generalizing several well-known methods and providing a concrete approach to obtain faster approximate counting and deterministic decision algorithms. This gives a new application of Waring rank, a classical topic in algebraic geometry with connections to algebraic complexity theory, to computer science. To illustrate the amenability and utility of this approach, we give a randomized $4.075^d \cdot \mathrm{poly}(n, \varepsilon^{-1})$-time algorithm for computing a $(1 + \varepsilon)$ approximation of the sum of the coefficients of the multilinear monomials in a degree-$d$ homogeneous $n$-variate polynomial with nonnegative coefficients. As an application of this we give a faster algorithm for approximately counting subgraphs of bounded treewidth, improving on earlier work of Alon et al. Along the way we give an exact answer to an open problem of Koutis and Williams and sharpen an upper bound on the size of perfectly balanced hash families given by Alon and Gutner.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Designing deterministic polynomial-space algorithms by color-coding multivariate polynomialsJournal of Computer and System Sciences, 2018
- Power sum decompositions of elementary symmetric polynomialsLinear Algebra and its Applications, 2016
- Progress on the symmetric Strassen conjectureJournal of Pure and Applied Algebra, 2015
- An upper bound for the Waring rank of a formArchiv der Mathematik, 2014
- On the parameterized complexity of the repetition free longest common subsequence problemInformation Processing Letters, 2012
- Finding and Counting Vertex-Colored SubtreesAlgorithmica, 2011
- Problems and results in extremal combinatorics—IDiscrete Mathematics, 2003
- Power Sums, Gorenstein Algebras, and Determinantal Loci1999
- Inclusion and exclusion algorithm for the Hamiltonian path problemInformation Processing Letters, 1993
- A note on the graph isomorphism counting problemInformation Processing Letters, 1979