SIGSAM sponsors awards for **Distinguished Papers** and **Distinguished Student Authors** at the annual
International Symposium on Symbolic and Algebraic Computation (ISSAC).

The award guidelines are available here.

If you have any corrections or can fill in any missing information please contact the Information Director on Infodir_SIGSAM@acm.org

**Author:** Pierre Lairez and Tristan Vaccon

**Title:** On p-adic differential equations with separation of variables

**Citation:**
The computation of a power series solution of a given ordinary differential equation is a basic problem in computer algebra. For a first-order ordinary differential equation with separation of variables and with p-adic coefficients, the authors of this paper give an optimal bound on the stability of the Newton iteration. The result applies to algorithms for manipulating
algebraic numbers over finite fields, for computing isogenies between elliptic curves, and for deterministically finding roots of polynomials in finite fields.

**Author:** Yi Zhang

**Title:** Contraction of Ore Ideals with Applications

**Author:** Matias Bender (with Jean-Charles Faugere, Ludovic Perret and Elias Tsigaridas)

**Title:** A Superfast Randomized Algorithm to Decompose Binary Forms

**Author:** Jean-Guillaume Dumas, Clément Pernet and Ziad Sultan

**Title:** Computing the rank profile matrix

**Citation:**
This paper studies forms of elimination that reveal the dependence structure of matrix rows, columns, or both simultaneously, significantly extending previous work. The authors categorize the forms of elimination including the permutation properties needed in pivot selection and placement to preserve the rank profile properties under various iterative and block approaches. In the course of this, a new strategy emerges to serve as a base case and substantially speed up rank profile preserving tiled elimination. The work is of particular significance because Gaussian elimination and the associated matrix factorization lie at the heart of a great deal of linear algebra, particularly in Computer Algebra.

**Author:** Sébastien Maulat (with Bruno Salvy)

**Title:**Formulas for Continued Fractions: An Automated Guess and Prove Approach

**Citation:**
The results of this paper are symbolic computation at its best, showing new ways for computers to discover and prove mathematical formulas, studied before for centuries. The paper gives a new algorithmic understanding of a classical problem, finding formulas for the continued fraction expansions of special functions. It is a completely new approach, and it turns insights from experimentation into algorithms, partially heuristic, but with algorithmic proof of correctness. This paper may be a start for a line of new research.

**Author:** Francois Le Gall

**Title:** Powers of Tensors and Fast Matrix Multiplication

**Citation:**
Multiplying matrices is one of the most fundamental tasks in
computational mathematics, it is in the core of most symbolic and
numerical algorithms. In 1969 Strassen proved a surprising result
improving the exponent in the complexity estimates of square
matrix multiplication from the straightforward log_2(8) to
log_2(7). Strassen's discovery started an active research area to
try to determine the minimal exponent omega.

Francois Le Gall's result is an important contribution to the complexity theory of matrix multiplication, partially because he slightly improves the best known upper-bound for omega.

Le Gall's contribution is twofold: First he gives a concise expression unifying prior approaches to obtain lower-bounds on tensor values. Second, he uses a convex relaxation of the resulting optimization problem, allowing fast computation of its optimum. As a result, he is able to improve the bound on omega in the fifths digit, and designed an efficient method that may used in future analysis and improvements.

**Author:** Shiyun Yang (with Arne Storjohann)

**Title:** Linear independence oracles and applications to low rank linear algebra

**Citation:**
The problem of solving systems of linear equations lies at the
heart of exact linear algebra. Storjohann and Yang show a new
algorithm for linear system solving over finite fields that is
especially fast for systems with low rank. They also show how to
apply their algorithm to compute the rank profiles of a matrix.
The algorithms are applicable to dense and sparse systems, and
automatically take advantage of sparsity when it is present to
speed the computation. Their method is based on the use of a novel
randomized data structure --- a linear independence oracle ---
which is both simple and surprisingly powerful. The paper is part
of Shiyun Yang's Master of Mathematics thesis and is primarily her
work.

**Author:** Carlos Arreche

**Title:** Computing the differential Galois group of a parameterized second-order linear differential equation

**Citation:**
The Galois theory of linear differential equations with parameters
is a very active research area. There is a great deal of
theoretical work that has been already developed, but the actual
complete algorithms are missing. Dreyfus showed how to compute
such a Galois group for a parameterized second order linear
differential equation in a special form, under some additional
technical conditions. These conditions were later removed by
Carlos Arreche, who is also the sole author of the paper that
extends these results for all second-order linear differential
equations with rational function coefficients. This algorithmic
extension is not only original but is also non-trivial.

**Authors:** Jingguo Bi, Qi Cheng, and J. Maurice Rojas

**Title:** Sub-Linear Root Detection, and New Hardness Results, for Sparse Polynomials Over Finite Fields

**Author:** Pierre Lairez (with Alin Bostan and Bruno Salvy)

**Title:** Creative Telescoping for Rational Functions Using the Griffiths-Dwork Method

**Author:** Qingdong Guo (with Mohab Safey El Din and Lihong Zhi)

**Title:** Computing Rational Solutions of Linear Matrix Inequalities

**Author:**Akos Seress

**Title:** Construction of 2-Closed M-Representations

**Author:** Wei Zhou (with George Labahn and Arne Storjohann).

**Title:** Computing Minimal Nullspace Bases

**Author:** Romain Lebreton (with Eric Schost).

**Title:** Algorithms for the Universal Decomposition Algebra

**Authors:** Wei Li, Xiao-Shan Gao, Cum-Ming Yuan

**Title:** Sparse Differential Resultant

**Author:** Armin Straub (with Jonathan Borwein).

**Title:** Special Values of Generalized Log-sine Integrals

**Authors:** Ioannis Emiris, Bernard Mourrain and Elias Tsigaridas

**Title:** The DMM bound: multivariate (aggregate) separation bounds

**Author:** Pierre-Jean Spaenlehauer (with Jean-Charles Faug�re and Mohab Safey El Din).

**Title:** Computing Loci of Rank Defects of Linear Matrices using Gr�bner Bases and Applications to Cryptology

**Author:**Chris Brown

**Title:**Fast Simplifications for Tarski Formulas

**Authors:** Wolf Daniel Andres and Jorge Mart\'{i}n Morales (with Viktor Levandovskyy)

**Title:** Principal Intersection and Bernstein-Sato Polynomial of Affine Variety

**Author:** YongJae Cha (with Mark van Hoeij)

**Title:** Liouvillian Solutions of Irreducible Linear Difference Equations

**Author:** Luca De Feo (with Eric Schost)

**Title:** Fast arithmetics in Artin-Schreier towers over finite fields

**Author:** Adam Strzebonski

**Title:** Real Root Isolation for Exp-Log Functions

**Author:** Adrien Poteaux (with Marc Rybowicz)

**Title:** On the Good Reduction of Puiseux Series and the Complexity of Newton-Puiseux Algorithm over Finite Fields

**Author:** Hongbo Li

**Title:** A recipe for symbolic geometric computing: long geometric product

**Author:** Marc Dohm (with Laurent Busé)

**Title:** Implicitization of Bi-homogeneous parametrizations of algebraic surfaces via linear syzygies

**Authors:** Ziming Li, Michael Singer, Min Wu and Dabin Zheng

**Title:**A Recursive Method for Determining the One-Dimensional Submodules of Laurent-Ore Modules

**Author:** Guénaël Renault

**Title:** Computation of the Splitting Field of a Dihedral Polynomial

**Authors:** Arno Eigenwillig, Vikram Sharma and Chee Yap

**Title:** Almost Tight Recursion Tree Bounds for the Descartes Method

**Authors:** Guillaume Moroz

**Title:** Complexity of the Resolution of Parametric Systems of Equations and Inequations

**Authors:** Erich Kaltofen and Pascal Koiran

**Title:** On the Complexity of Factoring Bivariate Supersparse (Lacunary) Polynomials

**Citation:**
A primary goal of the field
of computer algebra and symbolic computation is to find new
and better ways of computing with mathematical
objects. Polynomials are one of the most fundamental objects
in computer algebra, and yet a natural sparse representation
can present seemingly intractable complexity. More
specifically supersparse polynomials are polynomials defined
over the rational numbers with relatively few terms whose
exponents can be very large integers. While such polynomials
have a compact representation as a sum of non-zero terms,
some fundamental operations that we take for granted as
being easy for ordinary polynomials, such as evaluating at
integers, are generally infeasible.

Kaltofen and Koiran extend results of Hendrik Lenstra, Jr. for supersparse polynomials from the univariate to the bivariate case: they exhibit algorithms that can find all linear and quadratic factors of supersparse polynomials in polynomial time. They succeed by fusing classical computer algebra techniques of interpolation and modular reduction with modern randomized methods and deep bounds from algebraic number theory and Diophantine equations.

This work also contributes significantly to our theoretical understanding of algorithms for super-sparse polynomials by analyzing the general complexity of factoring and testing irreducibility. They show that a number of such problems are co-NP-hard, implying for example that a fast algorithm for such a problem would give a fast algorithm for integer factorization.

**Authors:** Bernard Mourrain and Philippe Trébuchet

**Title:** Generalized Normal Forms and Polynomial System Solving

**Citation:**
Solving systems of polynomial equations stands as one of
the great challenges of computer algebra. Rewriting a
polynomial in a simpler form using a set of polynomial
equations is an important and closely related
problem. This paper addresses the challenge of solving a
system by developing a better way to simplify a polynomial
with respect to that system.

The authors generalize the standard technique of simplification with respect to a monomial term ordering to create a framework of reducing families, reduction operators, and choice functions that leads to a generalized normal form for polynomials. Their generalization of term ordering builds on the Macaulay resultant and holds the potential for better numerical stability properties. They apply this framework to systems of polynomial equations with finitely many solutions where they use conventional numerical linear algebra techniques to compute the solution. The greater freedom in simplification afforded by this framework holds significant promise for improving our ability to solve systems of polynomial equations.

**Authors:** Xavier Dahan, Wenyuan Wu, and Yuzhen Xie (with Marc Moreno Maza and Eric Schost)

**Title:** Lifting techniques for triangular decompositions

**Author:** Christiaan van de Woestijne

**Title:** Deterministic equation solving over finite fields

**Authors:** Xavier Dahan and Eric Schost

**Title:** Sharp Estimates for Triangular Sets

**Citation:**
Solving systems of polynomial equations is a fundamental
problem in computational algebraic geometry with
applications throughout science and mathematics. Computer
scientists seek to quantify how difficult it is to solve a
system of equations, however until now, no one has succeeded
in bounding the difficulty (or complexity) by anything
better than pessimistic exponential bounds, except in a
special case where all the coordinates of the solutions are
polynomials in one distinguished coordinate (a so-called
primitive element).

Dahan and Schost have achieved something remarkable: they broke through the exponential barrier of complexity in the general case and obtained the polynomial bounds that were known previously only in the special case. Reducing a system of polynomial equations to triangular form allows its solutions to be computed more easily. However, the equations in the triangular form might be significantly larger than the original equations, perhaps exponentially larger. They showed that the size of the equations in a triangular form is at worst a quadratic function, and sometimes a linear function (if quotients of polynomials are permitted), of the size of the solution set of the original equations. This breakthrough enhances our understanding of this important problem by showing that the triangular form is in general smaller and less complicated than previously thought and therefore easier to compute and solve. In fact, such a bound directly yields better modular algorithms for computing triangular forms.

**Authors:** John P. May and Zhengfeng Yang (with Shuhong Gao, Erich Kaltofen, and Lihong Zhi)

**Title:** Approximate factorization of multivariate polynomials via differential equations

**Author:** Wayne Eberly

**Title:** Early Termination over Small Fields

**Citation:**
Solving systems of linear equations is the fundamental
problem of scientific computation. Over 2000 years ago, an
early Chinese book on mathematics described algorithms to
solve this problem. In our time, computer simulations of
physical processes require solving sparse linear systems
with huge numbers of unknowns. Researchers developed
specialized algorithms based on methods of Krylov to solve
these systems.

More recently, huge sparse systems of linear equations over finite fields have appeared in algorithms for factoring integers or for computing discrete logarithms. Krylov-based algorithms have been generalized to handle these systems. The security of modern cryptographic protocols that secure Internet communications and commerce rest their security partly on the difficulty of solving such linear systems, which increases our need to better understand such computations.

Experiments have suggested that a heuristic modification of Krylov-based algorithms improves performance in practice, but no theoretical analysis has been able to justify the experimental results or to prove the reliability of the heuristic. In his work, Eberly provides for the first time a theoretical justification for the observed experimental results, and he proves that we may rely on randomized Krylov-based algorithms without sacrificing performance. He provides new tight bounds for both the expected amount of look-ahead required when applying a randomized Lanczos algorithm, and the expected length of a sequence of zero-discrepancies that would be encountered when using a simple randomized version of Wiedemann's algorithm.

**Author:** Zhonggang Zeng

**Title:** Computing Multiple Roots of Inexact Polynomials

**Citation:**
Finding roots of polynomials has a long and rich history
in scientific computation. In most practical applications,
measuring the coefficients of the polynomials involved can
lead to errors that affect the accuracy and stability of
algorithms that find roots of these polynomials. While we
know excellent algorithms for finding single roots,
accurately computing multiple roots of polynomials remains
a challenge. Using for the first time the pejorative
manifold introduced by Kahan, Zeng developed an algorithm
that efficiently approximates multiple roots of
polynomials, even ones with inexact coefficients, without
resorting to slow calculations involving arbitrary
precision software floating point numbers. He has also
provided an efficient implementation that performs well in
experiments, thereby advancing the state of knowledge in
this field.

**Author:** Alicia Dickenstein and Ioannis Z. Emiris

**Title:** Multihomogeneous Resultant Matrices

**Citation:**
Solving systems of polynomial equations is a significant challenge
that lies at the heart of computer algebra and symbolic
computation. Dickenstein and Emiris have made a substantial
contribution towards the understanding of formulas, called resultants,
that solve systems of polynomial equations efficiently. They have
demonstrated how to explicitly compute such formulas in an important
special case and have described conditions when such formulas are the
best that can be attained. In this special case of multihomogeneous
resultants, they have shown how a combinatorial construction can be
made intrinsic.

**Author:** Arne Storjohann

**Title:** High-Order Lifting

**Citation:**
Since the nineteenth century, mathematicians have studied
matrices whose entries are numbers or polynomials in one
variable. Both mathematicians and computer scientists are
interested in solving equations involving matrices and in
finding natural ways to discover the structure of matrices by
converting them into certain ``normal forms''. Storjohann has
made a substantial contribution towards the development of
symbolic matrix algorithms that efficiently solve equations and
find normal forms of matrices of polynomials. His method of
``High-Order Lifting'' allows larger, complicated operations to
be broken down into smaller steps that rely primarily on the
simple yet efficient multiplication of matrices for the bulk of
the work. His method improves theoretical estimates and
practical performance of algorithms for these two problems as
well as other applications.