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.

Authors

• Kevin Pratt

Keywords

• Approximation algorithms
• Upper bound
• Complexity theory
• Computer science
• Geometry
• Two dimensional displays
• Symmetric matrices
• Exact Algorithm
• Waring Rank
• Lower Bound
• Diagonal Matrix
• Family Functioning
• Linear Form
• Cycle Length
• Characteristic Zero
• Algorithm For Problem
• Rank Of Matrix
• Random Function
• Linear Algebra
• Direct Sum
• Simple Cycle
• Group Algebra
• Graph Isomorphism
• Minimum Rank
• Hamiltonian Path
• Parametrized complexity
• Algebraic computation