Title：                 On the complexity of indefinite summation

Speaker：           Eugene Zima (Wilfrid Laurier University, Waterloo, Canada)

Time&Venue：   2019.07.19  14:30pm  N224

Abstract:：           The notion of dispersion plays a crucial role in the development of modern algorithms for indefinite summation. First introduced by Abramov in his classical work as the maximal integer distance between roots of the denominator of a reduced rational function, it has since been a key  notion in several algorithmic developments. For example many summation algorithms have the running time proportional to the dispersion (or square of the dispersion), which can be exponential in the bit size of their input.

We analyze the relation between the value of the dispersion and running time complexity of indefinite summation algorithms for different classes of summands, and show that the dependency of the running time on dispersion is non-essential (i.e. it is a feature of algorithms, not of the summation problems) in many cases. As an example of such behaviour we can mention  the following recent finding: if a non-rational hypergeometric term is summable, then the size of the result is polynomial in the size of the summand and we have an algorithm to find the sum in polynomial (in the input size) time.