Elements of Computer-Algebraic Analysis

Abstract: Algebraic Analysis has been coined by the Japanese group led by Mikio Sato. In recent years many constructions of Algebraic Analysis have been approached from the computer-algebraic point of view, with algorithms and their implementations. Extension of such an interaction from linear differential operators to linear difference, q-difference and q-differential operators we call Computer-Algebraic Analysis. The major object of study are systems of linear functional equations, their properties, solutions (including those in terms of generalized functions) and behaviour. Modern techniques of the ring theory, such as Gel'fand-Kirillov dimension and Ore localization as well as methods of homological algebra such as the purity filtration have been recently turned into algorithms with the help of computer algebra, where Gröbner bases play a prominent role. We will show the merits of these emerged techniques and discuss their applicability to concrete problems with the help of available implementations. In particular, computation of Jacobson normal form of a matrix over an Euclidean Ore domain, modelling of polynomial signals and the computation of Bernstein-Sato polynomials of affine varieties will be discussed in details.

Upper bounds on real roots and lower bounds for the permanent

Abstract: The complexity of the permanent polynomial is one of the central open problems in complexity theory. It is widely believed that the permanent is not computable by polynomial size arithmetic circuits. The author has shown that such a lower bound would follow a polynomial upper bound on the number of real (or integer) roots of a certain class of univariate polynomials: the sums of products of sparse polynomials. Note that a good upper bound for sparse polynomials (and products thereof) follows from Descartes' rule of signs. Sums of products are therefore arguably the next simplest case to consider, but very little seems to be known about their roots. In particular, the bounds that follow from Khovanskii's theory of fewnomials seem to be very far away from the truth. The goal of this tutorial is twofold :

i) To present a non-trivial upper bound on the number of real roots of sums of products of sparse polynomials. The Wronskian determinant is the main technical tool behind this bound; the proof technique should be of independent interest.

ii) To explain the connection with lower bounds for the permanent. It relies in particular on a fairly recent depth reduction result for arithmetic circuits due to Agrawal and Vinay (reduction to depth 4).

Algebraic Statistics

Abstract: Algebraic statistics advocates polynomial algebra as a tool for addressing problems in statistics and its applications. This connection is based on the fact that most statistical models are de fined either parametrically or implicitly via polynomial equations. The idea is summarized by the phrase "Statistical models are semialgebraic sets".

My tutorial will consist of a detailed study of two examples where the algebra/statistics connection has proven especially useful. First, I will explain how algebraic techniques arise in the study of phylogenetic models, which are used for reconstructing evolutionary trees. Then, I will explain how algebraic tools from the study of toric varieties are useful for analyzing contingency tables. I will indicate places where new methods in symbolic computation could lead to advances in algebraic statistics. Statistical prerequisites will be kept to an absolute minimum and the tutorial should be accessible to a broad audience.