Invited Speakers

Titles and Abstracts

Bill Chen
Nankai University, Tianjin, China.

The Art of Telescoping

Abstract:

We wish to give an overview of the background of telescoping algorithms developed by Gosper, Wilf, Zeilberger, et al. The idea of telescoping goes back to Leibniz, Euler and Abel. With the aid of computer algebra, the telescoping method has become a powerful tool in combinatorics. The creative telescoping is the parameterized version that leads to recurrence relations for definite summations. As an application, Koutschan, Kauers and Zeilberger proved the q-TSPP conjecture posed independently by Andrews and Robbins. The capability of the creative telescoping method has been intensively studied. Wilf and Zeilberger showed that the properness ensures the existence of a creative telescoper. The inverse problem, namely, under what conditions a creative telescoper can be found, turns out to be much harder. We shall discuss the recent developments due to Abramov, Chen, Chyzak, Feng, Fu and Li. The multi-variate analogue of telescoping is a challenging problem, with the Andrews-Paule identity as a benchmark example. We shall discuss various approaches to the multi-variate telescoping including the work of Chen and Singer as well as the implementations carried out by Apagodu, Zeilberger, Koutschan, Paule, Riese, and Schneider. Finally, as a multiplicative version of telescoping, we shall present an algorithmic approach to verify identities on multiple theta functions.


Lorenzo Robbiano
University of Genova, Genova, Italy.

Linear Algebra, Old and New

Abstract:

The purpose of my talk is to present old and new results which lie on the border between Linear Algebra and Computational Commutative Algebra. The main source is the recent book, Computational Linear and Commutative Algebra by Martin Kreuzer and myself (Springer 2016).

The talk starts by recalling some old results related to one endomorphism of a finitely generated vector space. Then we progress to considering families of pairwise commuting endomorphisms: this opens up a new world. The merits of this modern approach to linear algebra will be described. Among them, we will see the connection to many fundamental problems in computer algebra such as computing the primary decomposition of zero-dimensional ideals, and solving systems of polynomial equations.

The final part of the talk will be devoted to exhibiting a link between advanced tools in linear algebra and an old theme in algebraic geometry.


Virginia Vassilevska Williams
MIT, USA

Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication

Abstract:

We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the Group theoretic approach of Cohn and Umans. We define a generalization based on zeroing outs which subsumes these two approaches, which we call the Solar method, and an even more general method based on monomial degenerations, which we call the Galactic method. We then design a suite of techniques for proving lower bounds on the value of w, the exponent of matrix multiplication, which can be achieved by algorithms using many tensors T and the Galactic method. Some of our techniques exploit 'local' properties of T, like finding a sub-tensor of T which is so 'weak' that T itself couldn't be used to achieve a good bound on w; while others exploit 'global' properties, like T being a monomial degeneration of the structural tensor of a group algebra.
Our main result is that there is a universal constant L>2 such that a large class of tensors generalizing the Coppersmith-Winograd tensor CW[q] cannot be used within the Galactic method to show a bound on w better than L, for any q. We give evidence that previous lower-bounding techniques were not strong enough to show this. We also prove a number of complementary results along the way, including that for any group G, the structural tensor of C[G] can be used to recover the best bound on w which the Coppersmith-Winograd approach gets using CW[|G|−2] as long as the asymptotic rank of the structural tensor is not too large.
This is joint work with Josh Alman.