Date: Friday, October 04, 2013
Location: 3866 East Hall (4:10 PM to 5:00 PM)
Title: Subtractionfree 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 subtractionfree complexity, the version that allows addition, multiplication, and division, but not subtraction.
I will discuss efficient subtractionfree 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) starmesh transformations of (generalized) electric networks.
Comparison of (b) to the lower bound due to M. Jerrum and M. Snir shows that in subtractionfree computations, "division can be exponentially powerful."
This is joint work with D. Grigoriev and G. Koshevoy (arXiv:1307.8425).
Files:
Speaker: Sergey Fomin
Institution: U. Michigan
Event Organizer:
