Fast reconstruction of multivariate algebraic relations – CREAM

Relation reconstruction is a broad family of algorithmic problems. It ranges from solving linear systems which have particular patterns, to computing polynomials in several variables which satisfy approximation or interpolation constraints. The patterns and variables bring structure to the equations which implicitly define the sought relations. Relation reconstruction, as a core computational task, arises naturally in many areas of computer science, e.g. in path combinatorics, cryptography and error-correcting codes, where one commonly reconstructs algebraic relations from objects that hide them through implicit descriptions. The design and the implementation of highly efficient algorithms for this task is then of first importance and with high impact.

This project combines a complexity driven approach, through the lens of the algebraic structures underlying relation reconstruction, and the design of dedicated data representations and algorithmic techniques. The core goals are, first, to design the next generation of disruptive algorithms of quasi optimal complexity; second, to produce optimized open-source implementations; and lastly, to popularize and increase their impact by solving targeted instances arising in the aforementioned areas of computer science.

This project builds on recent results which allowed us to break through long-standing complexity barriers, for the moment on a restricted set of relations. It is organized around three grand objectives. The first two will bring the foundational algorithmic innovations, which will then be deployed and exploited in the last one to solve challenging instances of relation reconstruction.

The key innovative ideas developed in this project are efficient reductions to optimized subroutines such as matrix multiplication and polynomial multiplication in one variable, dimension reduction of the space where such relations are computed, and the exploitation of non-linear algebraic structures which arise in this algorithmic problem.