Geometry Seminar

Date: July 22, 2019

Time: 3:00PM - 4:00PM

Location: BLOC 628

Speaker: K. Pratt, Carnigie-Mellon U.

Title: Waring Rank, Parameterized and Exact Algorithms

Abstract: Given non-negative integers n and d, where n > d, what is the minimum number r such that there exist linear forms l_1, ... , l_r in C[x_1, ... ,x_n] so that l_1^d + ... + l_r^d is supported exactly on the set of all degree-d multi-linear monomials in x_1, ... , x_n? We show that this and related questions have intimate connections to the areas of parameterized and exact algorithms in computer science, generalizing earlier 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. As an application of this perspective we give 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 a lower bound on the size of perfectly balanced hash families given by Alon and Gutner.