|Date: Friday, October 04, 2013
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: Subtraction-free complexity
Abstract: The talk is motivated by the problem of dependence of computational complexity (more precisely, arithmetic circuit complexity of rational functions in several variables) on the set of allowed arithmetic operations. An important role in this context is played by the notion of subtraction-free complexity, the version that allows addition, multiplication, and division, but not subtraction.
I will discuss efficient subtraction-free algorithms for computing (a) Schur functions and their variations and (b) generating functions of spanning trees, both directed and undirected. These algorithms use, respectively, (a) cluster transformations of collections of matrix minors and (b) star-mesh transformations of (generalized) electric networks.
Comparison of (b) to the lower bound due to M. Jerrum and M. Snir shows that in subtraction-free computations, "division can be exponentially powerful."
This is joint work with D. Grigoriev and G. Koshevoy (arXiv:1307.8425).
Speaker: Sergey Fomin
Institution: U. Michigan