Waring Rank, Parameterized and Exact Algorithms

We show that the Waring rank (symmetric tensor rank) of a certain family of polynomials has intimate connections to the areas of parameterized and exact algorithms, generalizing some well-known methods and providing a concrete approach to obtain faster approximate counting and deterministic decision algorithms. To illustrate the amenability and utility of this approach, we give an algorithm for approximately counting subgraphs of bounded treewidth, improving on earlier work of Alon, Dao, Hajirasouliha, Hormozdiari, and Sahinalp. Along the way we give an exact answer to an open problem of Koutis and Williams and sharpen a lower bound on the size of perfectly balanced hash families given by Alon and Gutner.