| * Venue | E C G Sudarshan Hall |
| * Speaker | Prof. Mark Giesbrecht |
| * Title | Sparse Functional Decomposition |
| Affiliation | Dean, Faculty of Mathematics Professor, Cheriton School of Computer Science University of Waterloo |
| Abstract | We consider the algorithmic problem of the functional decomposition of sparse polynomials and rational functions. For example, given a sparse polynomial like f(x) = x^(5·2^100)+ 15x^(2^102+2^47)+ 90x^(3·2^100 +2^48)+243 x^(5.2^47)− 4x^(2^101)− 24x^(2^100+2^47)+ 270x^(2^101 +3·2^47) − 36x^(2^48) + 405x^(2^100 +2^49) + 1 we ask how to quickly determine whether it can be be quickly written as a composition of lower degree polynomials such as f(x)= g(h(x))= g◦h = (x^5− 4x^2 + 1)◦ (x^(2^100) + 3x^(2^47)). Mathematically, Erdos(1949), Schinzel(1987), and Zannier(2009) have made major progress in showing that polynomial roots and functional decom- positions of sparse polynomials, and even sparse rational functions, remain sparse (unlike factorizations for example). Computationally, we have had algorithms for functional decomposition of dense polynomials since Barton & Zippel (1976), though the first polynomial- time algorithms did not arrive until Kozen & Landau (1989) and a nearly linear time algorithm by von zur Gathen (1989), at least in the “tame” case, where the characteristic of the underlying field does not divide the degree. Algorithms for polynomial decomposition that exploit sparsity have re- mained elusive until now. We demonstrate new algorithms which provide very fast and simple solutions to many of these problems. Open algorithmic problems remain, including proving indecomposibility, and general rational function decomposition. And there is still considerable room to tighten spar- sity bounds in the underlying mathematics. We will explore connections to proving sparse divisibility, polynomial ir- reducibility, and other well-known open problems in the algebraic complexity of sparse polynomials. This is joint work with Saiyue Liu (UBC) and Daniel S. Roche (USNA). |
| * Announcement? | None |
| * Refreshments? | Before the event |
| * Honorarium? | Professor |
| Special Arrangements? | Digital Projection |
| * Host name and email |