Events for 07/22/2019 from all calendars
Geometry Seminar
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.