BARC talk by Kevin Pratt

Tuesday, 19 November 2019, Kevin Pratt, Doctoral Research Assistant at the Carnegie Mellon University in Pittsburgh, USA, will give a talk on "Waring rank, parameterized and exact algorithms".

Title:
Waring rank, parameterized and exact algorithms

Abstract:
The Waring rank of a degree-$d$ homogeneous polynomial $f$ is the minimum number of linear forms whose sum of $d$th powers is equal to $f$. For nonnegative integers $n$ and $d$, where $n \ge d$, define $A(n,d)$ as the minimum Waring rank of a degree-$d$ polynomial in $n$ variables that is supported exactly on the set of all degree-$d$ squarefree monomials. We show that this and related quantities have intimate connections to the areas of parameterized and exact algorithms, generalizing and improving previous 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.

Bio:
Kevin is a third-year computer science PhD student at Carnegie Mellon, advised by Ryan O'Donnell. He is interested in algebraic complexity theory and algebraic computation, in particular applications of algebra to parameterized and exact algorithms.