ISSAC Awards

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

Distinguished Paper Award

Author: Pierre Lairez and Tristan Vaccon

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

Link to publication

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.

Distinguished Student Author Awards

Author: Yi Zhang

Title: Contraction of Ore Ideals with Applications

Link to publication

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

Title: A Superfast Randomized Algorithm to Decompose Binary Forms

Link to publication

Distinguished Paper Award

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

Title: Computing the rank profile matrix

Link to publication

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.

Distinguished Student Author Award

Author: Sébastien Maulat (with Bruno Salvy)

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

Link to publication

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.

Distinguished Paper Award

Author: Francois Le Gall

Title: Powers of Tensors and Fast Matrix Multiplication

Link to publication

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.

Distinguished Student Author Awards

Author: Shiyun Yang (with Arne Storjohann)

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

Link to publication

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

Link to publication

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.

Distinguished Paper Award

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

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

Link to publication

Distinguished Student Author Awards

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

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

Link to publication

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

Title: Computing Rational Solutions of Linear Matrix Inequalities

Link to publication

Distinguished Paper Award

Author:Akos Seress

Title: Construction of 2-Closed M-Representations

Link to publication

Distinguished Student Author Awards

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

Title: Computing Minimal Nullspace Bases

Link to publication

Author: Romain Lebreton (with Eric Schost).

Title: Algorithms for the Universal Decomposition Algebra

Link to publication

Distinguished Paper Award

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

Title: Sparse Differential Resultant

Link to publication

Distinguished Student Author Awards

Author: Armin Straub (with Jonathan Borwein).

Title: Special Values of Generalized Log-sine Integrals

Link to publication

Distinguished Paper Award

Authors: Ioannis Emiris, Bernard Mourrain and Elias Tsigaridas

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

Link to publication

Distinguished Student Author Awards

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

Link to publication

Distinguished Paper Award

Author:Chris Brown

Title:Fast Simplifications for Tarski Formulas

Link to publication

Distinguished Student Author Awards

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

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

Link to publication

Author: YongJae Cha (with Mark van Hoeij)

Title: Liouvillian Solutions of Irreducible Linear Difference Equations

Link to publication

Author: Luca De Feo (with Eric Schost)

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

Link to publication

Distinguished Paper Award

Author: Adam Strzebonski

Title: Real Root Isolation for Exp-Log Functions

Link to publication

Distinguished Student Author Awards

Author: Adrien Poteaux (with Marc Rybowicz)

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

Link to publication

Distinguished Paper Award

Author: Hongbo Li

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

Link to publication

Distinguished Student Author Awards

Author: Marc Dohm (with Laurent Busé)

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

Link to publication

Distinguished Paper Award

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

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

Link to publication

Author: Guénaël Renault

Title: Computation of the Splitting Field of a Dihedral Polynomial

Link to publication

Distinguished Student Author Awards

Authors: Arno Eigenwillig, Vikram Sharma and Chee Yap

Title: Almost Tight Recursion Tree Bounds for the Descartes Method

Link to publication

Authors: Guillaume Moroz

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

Link to publication

Distinguished Paper Award

Authors: Erich Kaltofen and Pascal Koiran

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

Link to publication

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

Link to publication

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.

Distinguished Student Author Awards

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

Title: Lifting techniques for triangular decompositions

Link to publication

Author: Christiaan van de Woestijne

Title: Deterministic equation solving over finite fields

Link to publication

Distinguished Paper Award

Authors: Xavier Dahan and Eric Schost

Title: Sharp Estimates for Triangular Sets

Link to publication

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.

Distinguished Student Author Awards

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

Title: Approximate factorization of multivariate polynomials via differential equations

Link to publication

Distinguished Paper Award

Author: Wayne Eberly

Title: Early Termination over Small Fields

Link to publication

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

Link to publication

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.

Distinguished Paper Award

Author: Alicia Dickenstein and Ioannis Z. Emiris

Title: Multihomogeneous Resultant Matrices

Link to publication

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

Link to publication

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.