2.1.1 Basic computable objects and algorithms

The basic computable objects and algorithms we study, use, optimize or develop are among the most classical ones in computer algebra and are studied by many people around the world: they mainly focus on basic computer arithmetic, linear algebra, lattices, and both polynomial system and differential system solving.

In the context of OURAGAN, it is important to avoid reinventing the wheel and to re-use wherever possible existing objects and algorithms, not necessarily developed in our team so that the main effort is focused on finding good formulations/modelisations for an efficient use. Also, our approach for the development of basic computable objects and algorithms is application driven and follows a simple strategy : use the existing tools in priority, develop missing tools when required and then optimize the critical operations. First, for some selected problems, we do propose and develop general key algorithms (isolation of real roots of univariate polynomials, parametrisations of solutions of zero-dimensional polynomial systems, solutions of parametric equations, equidimensional decompositions, etc.) in order to complement the existing set computable objects developed and studied around the world (Gröbner bases, resultants 75, subresultants 95, critical point methods 52, etc.) which are also deeply used in our developments. Second, for a selection of well-known problems, we propose different computational strategies (for example the use of approximate arithmetic to speed up LLL algorithm or root isolators, still certifying the final result). Last, we propose specialized variants of known algorithms optimized for a given problem (for example, dedicated solvers for degenerated bivariate polynomials to be used in the computation of the topology of plane curves).

In the activity of OURAGAN, many key objects or algorithms around the resolution of algebraic systems are developed or optimized within the team, such as the resolution of polynomials in one variable with real coefficients 11417, rational parameterizations of solutions of zero-dimensional systems with rational coefficients 6016 or discriminant varieties for solving systems depending on parameters 14, but we are also power users of existing software (mainly Sage 1, Maple 2, Pari-GP 3,Snappea 4) and libraries (mainly gmp 5, mpfr 6, flint 7, arb 8, etc.) to which we contribute when it makes sense.

For our studies in number theory and applications to the security of cryptographic systems, our team works on three categories of basic algorithms: discrete logarithm computations 109 (for example to make progress on the computation of class groups in number fields 96), network reductions by means of LLL variants 85 and, obviously, various computations in linear algebra, for example dedicated to almost sparse matrices 110.

For the algorithmic approach to algebraic analysis of functional equations 56112113, we developed the effective study of both module theory and homological algebra 144 over certain noncommutative polynomial rings of functional operators 4, of Stafford's famous theorems on the Weyl algebras 134, of the equidimensional decomposition of functional systems 131, etc.

Finally, we study effective methods in algebraic topology, with a view towards the computation of normal forms or bases, and the construction of small resolutions of various algebraic structures: monoids and groups, algebras and operads, categories and higher structures, etc. The construction methods can come from combinatorial group theory (rewriting, Garside structures), combinatorial algebra (Gröbner bases), or homological algebra (Koszul duality, Morse theory). We explore potential deep foundational connexions between these different points of view, to unify, generalise and improve them.

2.1.2 Computational Number Theory

Many frontiers between computable objects, algorithms (above section), computational number theory and applications, especially in cryptography are porous. However, one can classify our work in computational number theory into two classes of studies : computational algebraic number theory and (rigorous) numerical computations in number theory.

Our work on rigorous numerical computations is somehow a transverse activity in Ouragan : floating point arithmetic is used in many basic algorithms we develop (root isolation, LLL) and is thus present in almost all our research directions. However there are specific developments that could be labelized Number Theory, in particular contributions to numerical evaluations of $L$-functions which are deeply used in many problems in number theory (for example the Riemann Zeta function). We participate, for example to the L-functions and Modular Forms Database9 a world wide collaborative project.

Our work in computational algebraic number theory is driven by the algorithmic improvement to solve presumably hard problems relevant to cryptography. The use of number-theoretic hard problems in cryptography dates back to the invention of public-key cryptography by Diffie and Hellman 81, where they proposed a first instantiation of their paradigm based on the discrete logarithm problem in prime fields. The invention of RSA 142, based on the hardness of factoring came as a second example. The introduction of discrete logarithms on elliptic curves 11550 only confirmed this trend.

These crypto-systems attracted a lot of interest on the problems of factoring and discrete log. Their study led to the invention of fascinating new algorithms that can solve the problems much faster than initially expected :

• the elliptic curve method (ECM) 150
• the quadratic field for factoring 128 and its variant for discrete log called the Gaussian integers method 123
• the number field sieve (NFS) 151

Since the invention of NFS in the 90’s, many optimizations of this algorithm have been performed. However, an algorithm with better complexity hasn’t been found for factoring and discrete logarithms in large characteristic.

While factorization and discrete logarithm problems have a long history in cryptography, the recent post-quantum cryptosystems introduce a new variety of presumably hard problems/objects/algorithms with cryptographic relevance: the shortest vector problem (SVP), the closest vector problem (CVP) or the computation of isogenies between elliptic curves, especially in the supersingular case.

Members of OURAGAN started working on the topic of discrete logarithms around 1998, with several computation records that were announced on the NMBRTHRY mailing list. In large characteristic, especially for the case of prime fields, the best current method is the number field sieve (NFS) algorithm. In particular, they published the first NFS based record computation13. Despite huge practical improvements, the prime field case algorithm hasn't really changed since that first record. Around the same time, we also presented small characteristic computation record based on simplifications of the Function Field Sieve (FFS) algorithm  108.

In 2006, important changes occurred concerning the FFS and NFS algorithms, indeed, while the algorithms only covered the extreme case of constant characteristic and constant extension degree, two papers extended their ranges of applicability to all finite fields. At the same time, this permitted a big simplification of the FFS, removing the need for function fields.

Starting from 2012, new results appeared in small characteristic. Initially based on a simplification of the 2006 result, they quickly blossomed into the Frobenial representation methods, with quasi-polynomial time complexity 109, 97.

An interesting side-effect of this research was the need to revisit the key sizes of pairing-based cryptography. This type of cryptography is also a topic of interest for OURAGAN. In particular, it was introduced in 2000 12.

The computations of class groups in number fields has strong links with the computations of discrete logarithms or factorizations using the NFS (number field sieve) strategy which as the name suggests is based on the use of number fields. Roughly speaking, the NFS algorithm uses two number fields and the strategy consists in choosing number fields with small sized coefficients in their definition polynomials. On the contrary, in class group computations, there is a single number field, which is clearly a simplification, but this field is given as input by some fixed definition polynomial. Obviously, the degree of this polynomial as well as the size of its coefficients are both influencing the complexity of the computations so that finding other polynomials representing the same class group but with a better characterization (degree or coefficient's sizes) is a mathematical problem with direct practical consequences. We proposed a method to address the problem 96, but many issues remain open.

Computing generators of principal ideals of cyclotomic fields is also strongly related to the computation of class groups in number fields. Ideals in cyclotomic fields are used in a number of recent public-key cryptosystems. Among the difficult problems that ensure the safety of these systems, there is one that consists in finding a small generator, if it exists, of an ideal. The case of cyclotomic fields is considered 55.

2.1.3 Topology in small dimension

2.1.4 Algebraic analysis of functional systems

Systems of functional equations or simply functional systems are systems whose unknowns are functions, such as systems of ordinary or partial differential equations, of differential time-delay equations, of difference equations, of integro-differential equations, etc.

Numerical aspects of functional systems, especially differential systems, have been widely studied in applied mathematics due to the importance of numerical simulation issues.

Complementary approaches, based on algebraic methods, are usually upstream or help the numerical simulation of systems of functional systems. These methods also tackle a different range of questions and problems such as algebraic preconditioning, elimination and simplification, completion to formal integrability or involution, computation of integrability conditions and compatibility conditions, index reduction, reduction of variables, choice of adapted coordinate systems based on symmetries, computation of first integrals of motion, conservation laws and Lax pairs, Liouville integrability, study of the (asymptotic) behavior of solutions at a singularity, etc. Although not yet very popular in applied mathematics, these theories have lengthy been studied in fundamental mathematics and were developed by Lie, Cartan, Janet, Ritt, Kolchin, Spencer, etc. 104112113116141129.

Over the past years, certain of these algebraic approaches to functional systems have been investigated within an algorithmic viewpoint, mostly driven by applications to engineering sciences such as mathematical systems theory and control theory. We have played a role towards these effective developments, especially in the direction of an algorithmic approach to the so-called algebraic analysis112, 113, 56, a mathematical theory developed by the Japanese school of Sato, which studies linear differential systems by means of both algebraic and analytic methods. To develop an effective approach to algebraic analysis, we first have to make algorithmic standard results on rings of functional operators, module theory, homological algebra, algebraic geometry, sheaf theory, category theory, etc., and to implement them in computer algebra systems. Based on elimination theory (Gröbner or Janet bases 104, 73, 143, differential algebra 5886, Spencer's theory 129, etc.), in 4, 5, we have initiated such a computational algebraic analysis approach for general classes of functional systems (and not only for holonomic systems as done in the literature of computer algebra 73). Based on the effective aspects to algebraic analysis approach, the parametrizability problem 4, the reduction and (Serre) decomposition problems 5, the equidimensional decomposition 131, Stafford's famous theorems for the Weyl algebras 134, etc., have been studied and solutions have been implemented in Maple, Mathematica, and GAP725. But these results are only the first steps towards computational algebraic analysis, its implementation in computer algebra systems, and its applications to mathematical systems, control theory, signal processing, mathematical physics, etc.

Rigorous numerical computations

Some studies in this area will be driven by some other directions, for example, the rigorous evaluation of non algebraic functions on algebraic varieties might become central for some of our work on topology in small dimension (volumes of varieties, drawing of amoeba) or control theory (approximations of discriminant varieties) are our two main current sources of interesting problems. In the same spirit, the work on $L$-functions computations (extending the computation range, algorithmic tools for computing algebraic data from the $L$ function) will naturally follow.

On the other hand, another objective is to extend existing results on periods of algebraic curves to general curves and higher dimensional varieties is a general promising direction. This project aims at providing tools for integration on higher homology groups of algebraic curves, ie computing Gauss-Manin connections. It requires good understanding of their topology, and more algorithmic tools on differential equations.

Character varieties

The brute force approach to computable objects from topology of small dimension will not allow any significant progress. As explained above, the systems that arise from these problems are simply outside the range of doable computations. We still continue the work in this direction by a four-fold approach, with all three directions deeply inter-related. First, we focus on a couple of especially meaningful (for the applications) cases, in particular the 3-dimensional manifold called Whitehead link complement. At this point, we are able to make steps in the computation and describe part of the solutions 89, 101; we hope to be able to complete the computation using every piece of information to simplify the system. Second, we continue the theoretical work to understand more properties of these systems 87. These properties may prove how useful for the mathematical understanding is the resolution of such systems - or at least the extraction of meaningful information. This approach is for example carried on by Falbel and his work on configuration of flags 90, 92. Third, we position ourselves as experts in the know-how of this kind of computations and natural interlocutors for colleagues coming up with a question on such a computable object (see 98 and 101). This also allows us to push forward the kind of computation we actually do and make progress in the direction of the second point. We are credible interlocutors because our team has the blend of theoretical knowledge and computational capabilities that grants effective resolutions of the problems we are presented. And last, we use the knowledge already acquired to pursue our theoretical study of the CR-spherical geometry 80, 91, 88.

Another direction of work is the help to the community in experimental mathematics on new objects. It involves downsizing the system we are looking at (for example by going back to systems coming from hyperbolic geometry and not CR-spherical geometry) and get the most out of what we can compute, by studying new objects. An example of this research direction is the work of Guilloux around the volume function on deformation varieties. This is a real-analytic function defined on the varieties we specialized in computing. Being able to do effective computations with this function led first to a conjecture 100. Then, theoretical discussions around this conjecture led to a paper on a new approach to the Mahler measure of some 2-variables polynomials 99. In turn, this last paper gave a formula for the Mahler measure in terms of a function akin to the volume function applied at points in an algebraic variety whose moduli of coordinates are 1. The OURAGAN team has the expertise to compute all the objects appearing in this formula, opening the way to another area of application. This area is deeply linked with number theory as well as topology of small dimension. It requires all the tools at disposition within OURAGAN.

Knot theory

We will carry on the exhaustive search for the lexicographic degrees for the rational knots. They correspond to trigonal space curves: computations in the braid group $B_3$, explicit parametrization of trigonal curves corresponding to "dessins d'enfants", etc. The problem seems much more harder when looking for more general knots.

On the other hand, a natural direction would be: given an explicit polynomial space curve, determine the under/over nature of the crossings when projecting, draw it and determine the known knot 16 it is isotopic to.

Vizualisation and Computational Geometry

As mentioned above, the drawing of algebraic curves and surfaces is a critical action in OURAGAN since it is a key ingredient in numerous developments. In some cases, one will need a fully certified study of the variety for deciding existence of solutions (for example a region in a robot's parameter's space with solutions to the DKP above or deciding if some variety crosses the unit polydisk for some stability problems in control-theory), in some other cases just a partial but certified approximation of a surface (path planning in robotics, evaluation of non algebraic functions over an algebraic variety for volumes of knot complements in the study of character varieties).

On the one hand, we will contribute to general tools like ISOTOP 17 under the supervision of the GAMBLE project-team and, on the other hand, we will propose ad-hoc solutions by gluing some of our basic tools (problems of high degrees in robust control theory). The priority is to provide a first software that implements methods that fit as most as possible the very last complexity results we got on several (theoretical) algorithms for the computation of the topology of plane curves.

A particular effort will be devoted to the resolution of overconstraint bivariate systems which are useful for the studies of singular points and to polynomials systems in 3 variables in the same spirit : avoid the use of Gröbner basis and propose a new algorithm with a state-of-the-art complexity and with a good practical behavior.

In parallel, one will have to carefully study the drawing of graphs of non algebraic functions over algebraic complex surfaces for providing several tools which are useful for mathematicians working on topology in small dimension (a well known example is the drawing of amoebia, a way of representing a complex curve on a sheet of paper).

7.1.1 ISOTOP

• Name:
  Topology and geometry of planar algebraic curves
• Keywords:
  Topology, Curve plotting, Geometric computing
• Functional Description:
  Isotop is a Maple software for computing the topology of an algebraic plane curve, that is, for computing an arrangement of polylines isotopic to the input curve. This problem is a necessary key step for computing arrangements of algebraic curves and has also applications for curve plotting. This software has been developed since 2007 in collaboration with F. Rouillier from Inria Paris - Rocquencourt.
• URL:
  https://­isotop.­gamble.­loria.­fr/
• Publications:
  hal-00809430, hal-00809425, inria-00329754, inria-00580431, hal-00992634, hal-01342211, inria-00425383, inria-00517175, hal-01468796, hal-00977671
• Contact:
  Marc Pouget
• Participants:
  Luis Penaranda, Marc Pouget, Sylvain Lazard

7.1.2 RS

• Functional Description:
  Real Roots isolation for algebraic systems with rational coefficients with a finite number of Complex Roots
• URL:
  https://­team.­inria.­fr/­ouragan/­software/
• Contact:
  Fabrice Rouillier
• Participant:
  Fabrice Rouillier

7.1.3 A NewDsc

• Name:
  A New Descartes
• Keyword:
  Scientific computing
• Functional Description:
  Computations of the real roots of univariate polynomials with rational coefficients.
• URL:
  https://­anewdsc.­mpi-inf.­mpg.­de
• Authors:
  Fabrice Rouillier, Alexander Kobel, Michael Sagraloff
• Contact:
  Fabrice Rouillier
• Partner:
  Max Planck Institute for Software Systems

7.1.4 SIROPA

• Keywords:
  Robotics, Kinematics
• Functional Description:
  Library of functions for certified computations of the properties of articulated mechanisms, particularly the study of their singularities
• URL:
  http://­siropa.­gforge.­inria.­fr/
• Authors:
  Damien Chablat, Fabrice Rouillier, Guillaume Moroz, Philippe Wenger
• Contact:
  Guillaume Moroz
• Partner:
  LS2N

7.1.5 MPFI

• Keyword:
  Arithmetic
• Functional Description:
  MPFI is a C library based on MPFR and GMP for multi precision floating point arithmetic.
• URL:
  http://­mpfi.­gforge.­inria.­fr
• Contact:
  Fabrice Rouillier

7.2.1 Visualisation of limit sets

Character varieties are studied in the team as an interesting algebraic object. This study is completed by an effort to understand the geometrical meaning of each points in some carefully chosen character varieties. One approach to this problem is the construction of geometric structures.

Another approach is the study of limit sets associated to such points and their deformations when moving in the character variety. Those are fractal objects in the 3-sphere ${𝕊}^3$, which shares numerous properties with the usual fractal from complex dynamics. In our work, we study this limit sets first and foremost in an experimental way, leading to a "Landscape of limit sets" ( http://limit-sets.imj-prg.fr). The computation of such visualisations leverages the theoretical properties of these limit sets, certified numerical approximations. An improved version of the visualisation is in progress, and will use the theory of automatic groups as well as new and more efficient parametrizations of the objects of study.

The experimental approach in turns inform the theoretical one. One important new step, bridging the two approaches, is done in 45.

On the Ore extension ring of differential time-varying delay operators

.

In 40, we propose an algebraic method to study linear differential time-varying delay (DTVD) systems. Our goal is to give an effective construction of the ring of DTVD operators as an Ore extension, thanks to the concept of skew polynomial rings developed by Ore in the 30s. Some algebraic properties of the DTVD operators ring are analyzed, such as its Noetherianity, its homological and Krull dimensions, and the existence of Gröbner bases, all given in terms of the time-varying delay function. The algebraic analysis framework for linear systems theory allows us to study linear DTVD systems and essential properties such as the existence of autonomous elements, controllability, parametrizability, flatness, etc., through methods coming from module theory, homological algebra, and constructive algebra.

An integro-differential operator approach to linear differential systems

.

In 38, we initiate a new algebraic analysis approach to linear differential systems based on rings of integro-differential operators. Within this algebraic analysis approach, we first interpret the method of variations of constants as an operator identity. Using this result, we show that the module associated with a state-space representation of a linear system is the same as the one associated with its standard convolution representation. This finitely presented module over the ring of integro-differential operators is proved to be stably free. Finally, we show how the reachability property can be expressed within this algebraic analysis approach.

An Integro-differential-delay Operator Approach to Transformations of Linear Differential Time-delay Systems

.

In 37, we further develop the study of rings of integro-differential-delay operators considered as noncommutative polynomial algebras satisfying standard calculus identities. Within the algebraic analysis approach, we show that transformations and reductions of linear differential time-delay systems can be interpreted as homomorphisms and isomorphisms of finitely presented left modules over an algebra of integro-differential-delay operators. In particular, we show how Fiagbedzi-Pearson's transformation can be found again and generalized. This transformation maps the solutions of a first-order differential linear system with state and input delays to the solutions of a purely state-space linear system. Fiagbedzi-Pearson's transformation reduces to the well-known Artstein's reduction when the system has no state delay and yields an isomorphism of the solution spaces.

An Integro-differential Operator Approach to Linear State-space Systems

.

In 36, the algebraic analysis approach to linear state-space systems is further developed using rings of integro-differential operators. The module structure of linear state-space systems is investigated over these rings. The module associated with a linear state-space system is shown to be the direct sum of the stably free module defined by the linear system without inputs and the free module defined by the inputs of the system.

Computation of Koszul homology and application to involutivity of partial differential systems

.

The formal integrability of systems of partial differential equations plays a fundamental role in different analysis and synthesis problems for both linear and nonlinear differential control systems. In 32, following Spencer's theory, to test the formal integrability of a system of partial differential equations, we must study when the symbol of the system, namely, the top-order part of the linearization of the system, is 2-acyclic or involutive, i.e., when certain Spencer cohomology groups vanish. Combining the fact that Spencer cohomology is dual to Koszul homology and symbolic computation methods, we show how to effectively compute the homology modules defined by the Koszul complex of a finitely presented module over a commutative polynomial ring. These results are implemented using the OreMorphisms package. We then use these results to effectively characterize 2-acyclicity and involutivity of the symbol of a linear system of partial differential equations. Finally, we show explicit computations on two standard examples.

Efficient sampling in spectrahedra and volume approximation

.

In 21, we present algorithmic, complexity, and implementation results on the problem of sampling points from a spectrahedron, that is, the feasible region of a semidefinite program. Our main tool is geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spectrahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spectrahedra that experimentally show faster mixing times than methods currently employed either in theoretical studies or in applications, including the popular family of Hit-and-Run walks. The different random walks offer a variety of advantages, thus allowing us to efficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applications of independent interest: (i) approximate the volume of a spectrahedron, and (ii) compute the expectation of functions coming from robust optimal control. We exploit efficient linear algebra algorithms and implementations to address the aforementioned computations in very high dimension. In particular, we provide a C++ open source implementation of our methods that scales efficiently, for the first time, up to dimension 200. We illustrate its efficiency on various data sets.

On the Complexity of the Plantinga-Vegter Algorithm

.

In 23, we introduce a general toolbox for precision control and complexity analysis of subdivision based algorithms in computational geometry. We showcase the toolbox on a well known example from this family; the adaptive subdivision algorithm due to Plantinga and Vegter. The only existing complexity estimate on this rather fast algorithm was an exponential worst-case upper bound for its interval arithmetic version. We go beyond the worst-case by considering smoothed analysis, and prove polynomial time complexity estimates for both interval arithmetic and finite precision versions of the Plantinga-Vegter algorithm. The employed toolbox is a blend of robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this combination of tools from different disciplines would prove useful for understanding complexity aspects of the broad family of subdivision based algorithms in computational geometry.

On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric Curves

.

Given a parametric polynomial curve $\gamma :[a,b]\to Rn$, how can we sample a random point $x\in im\left(\gamma \right)$ in such a way that it is distributed uniformly with respect to the arc-length? Unfortunately, we cannot sample exactly such a point—even assuming we can perform exact arithmetic operations. So we end up with the following question: how does the method we choose affect the quality of the approximate sample we obtain? In practice, there are many answers. However, in theory, there are still gaps in our understanding. In 31, we address this question from the point of view of complexity theory, providing bounds in terms of the size of the desired error.

PTOPO: Computing the Geometry and the Topology of Parametric Curves

.

In 27, we consider the problem of computing the topology and describing the geometry of a parametric curve in $R^n$. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most $d$ and maximum bitsize of coefficients $\tau$, then the worst case bit complexity of PTOPO is $O_B(n{d}^6+n{d}^5\tau +d^4(n^2+n\tau )+d^3(n^2\tau +n^3)+n^3{d}^2\tau )$. This bound matches the current record bound $O_B(d^6+d^5\tau )$ for the problem of computing the topology of a plane algebraic curve given in implicit form. For plane and space curves, if $N=max(d,\tau )$, the complexity of PTOPO becomes $O_B\left(N^6\right)$, which improves the stateof-the-art result, due to Alcázar and Díaz-Toca [CAGD10], by a factor of $N^{1}0$. In the same time complexity, we obtain a graph whose straight-line embedding is isotopic to the curve. However, visualizing the curve on top of the abstract graph construction, increases the bound to $OB\left(N^7\right)$. For curves of general dimension, we can also distinguish between ordinary and non-ordinary real singularities and determine their multiplicities in the same expected complexity of PTOPO by employing the algorithm of Blasco and Pérez-Díaz [CAGD'19]. We have implemented PTOPO in maple for the case of plane and space curves. Our experiments illustrate its practical nature.

Bounds for polynomials on algebraic numbers and application to curve topology

.

Let $P\in Z[X,Y]$ be a given square-free polynomial of total degree d with integer coefficients of bitsize less than τ, and let $VR\left(P\right):=(x,y)\in R^2,P(x,y)=0$ be the real planar algebraic curve implicitly defined as the vanishing set of P. In 25, we give a deterministic algorithm to compute the topology of $VR\left(P\right)$ in terms of a simple straight-line planar graph G that is isotopic to $VR\left(P\right)$. The upper bound on the bit complexity of our algorithm is in $\tilde{O}(d^5\tau +d^6)$ which matches the current record bound for the problem of computing the topology of a planar algebraic curve. However, compared to existing algorithms with comparable complexity, our method does not consider any change of coordinates, and more importantly the returned simple planar graph $G$ yields the cylindrical algebraic decomposition information of the curve in the original coordinates. Our result is based on two main ingredients: First, we derive amortized quantitative bounds on the roots of polynomials with algebraic coefficients.

Beyond Worst-Case Analysis for Root Isolation Algorithms

.

Isolating the real roots of univariate polynomials is a fundamental problem in symbolic computation and it is arguably one of the most important problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, the worst-case analysis of root-finding algorithms does not correlate with their practical performance. In 33, we develop a smoothed analysis framework for polynomials with integer coefficients to bridge the gap between the complexity estimates and the practical performance. In this setting, we derive that the expected bit complexity of Descartes solver to isolate the real roots of a polynomial, with coefficients uniformly distributed, is ÕB(d2 + dτ), where d is the degree of the polynomial and τ the bitsize of the coefficients.

On Polynomial Modular Number Systems over $\mathbb{Z}/p\mathbb{Z}$

.

Since their introduction in 2004,Polynomial Modular Number Systems (PMNS) have become a very interesting tool for implementing cryptosys- tems relying on modular arithmetic in a secure and efficient way. However, while their implementation is simple, their parameterization is not trivial and relies on a suitable choice of the polynomial on which the PMNS operates. The initial proposals were based on particular binomials and trinomials. But these polynomials do not always provide systems with interesting characteristics such as small digits, fast reduction, etc. In 19, we study a larger family of polynomials that can be exploited to design a safe and efficient PMNS. To do so, we first state a complete existence theorem for PMNS which provides bounds on the size of the digits for a generic polynomial, significantly improving previous bounds. Then, we present classes of suitable polynomials which provide numerous PMNS for safe and efficient arithmetic.

Generating Very Large RNS Bases

.

Residue Number Systems (RNS) are proven to be effective in speeding up computations involving additions and products. For these representations, there exists efficient modular reduction algorithms that can be used in the context of arithmetic over finite fields or modulo large numbers, especially when used in the context of cryptographic engineering. Their independence allows random draws of bases, which also makes it possible to protect against side-channel attacks, or even to detect them using redundancy. These systems are easily scalable, however the existence of large bases for some specific uses remains a difficult question. In 18, we present four techniques to extract RNS bases from specific sets of integers, giving better performance and flexibility to previous works in the litterature. While our techniques do not allow to solve efficiently every possible case, we provide techniques to provably and efficiently find the largest possible available RNS bases in several cases, improving the state-of-the-art on various works of the recent literature.

A classification of ECM-friendly families using modular curves

.

In 20, we establish a link between the classification of ECM-friendly curves and Mazur’s program $B$, which consists in parameterizing all the families of elliptic curves with exceptional Galois image. Building upon two recent works which treated the case of congruence subgroups of prime-power level which occur for infinitely many $j$-invariants, we prove that there are exactly 1525 families of rational elliptic curves with distinct Galois images which are cartesian products of subgroups of prime-power level. This makes a complete list of rational families of ECM-friendly elliptic curves, out of which less than 25 were known in the literature. We furthermore refine a heuristic of Montgomery to compare these families and conclude that the best 4 families which can be put in $a=-1$ twisted Edwards’ form are new.

Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection

.

In 34, we propose (honest verifier) zero-knowledge arguments for the modular subset sum problem. Previous combinatorial approaches, notably one due to Shamir, yield arguments with cubic communication complexity (in the security parameter). More recent methods, based on the MPC-in-the-head technique, also produce arguments with cubic communication complexity. We improve this approach by using a secret-sharing over small integers (rather than modulo q) to reduce the size of the arguments and remove the prime modulus restriction. Since this sharing may reveal information on the secret subset, we introduce the idea of rejection to the MPC-in-the- head paradigm. Special care has to be taken to balance completeness and soundness and preserve zero-knowledge of our arguments. We combine this idea with two techniques to prove that the secret vector (which selects the subset) is well made of binary coordinates. Our new protocols achieve an asymptotic improvement by producing arguments of quadratic size. This improvement is also practical: for a 256-bit modulus q, the best variant of our protocols yields 13 KB arguments while previous proposals gave 1180 KB arguments, for the best general protocol, and 122 KB, for the best protocol restricted to prime modulus. Our techniques can also be applied to vectorial variants of the subset sum problem and in particular the inhomogeneous short integer solution (ISIS) problem for which they provide an efficient alternative to state-of-the-art protocols when the underlying ring is not small and NTT-friendly. We also show the application of our protocol to build efficient zero-knowledge arguments of plaintext and/or key knowledge in the context of fully-homomorphic encryption. When applied to the TFHE scheme, the obtained arguments are more than 20 times smaller than those obtained with previous protocols. Eventually, we use our technique to construct an efficient digital signature scheme based on a pseudorandom function due to Boneh, Halevi, and Howgrave-Graham.

Computing groups of Hecke characters

.

In 35, we describe algorithms to represent and compute groups of Hecke characters. We make use of an idèlic point of view and obtain the whole family of such characters, including transcendental ones. We also show how to isolate the algebraic characters, which are of particular interest in number theory. This work has been implemented in Pari/GP, and we illustrate our work with a variety of explicit examples using our implementation.

Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

.

Elliptic bases, introduced by Couveignes and Lercier in 2009, give an elegant way of representing finite field extensions. A natural question which seems to have been considered independently by several groups is to use this representation as a starting point for small characteristic finite field discrete logarithm algorithms. This idea has been recently proposed by two groups working on it, in order to achieve provable quasi-polynomial time for discrete logarithms in small characteristic finite fields. In this paper, we don't try to achieve a provable algorithm but, instead, investigate the practicality of heuristic algorithms based on elliptic bases. In 26, our key idea, is to use a different model of the elliptic curve used for the elliptic basis that allows for a relatively simple adaptation of the techniques used with former Frobenius representation algorithms. We haven't performed any record computation with this new method but our experiments with the field F 3 1345 indicate that switching to elliptic representations might be possible with performances comparable to the current best practical methods.

Functional norms, condition numbers and numerical algorithms in algebraic geometry

.

In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand in order to optimize accuracy or computational complexity. In numerical polynomial algebra, a single norm (attributed to Weyl) dominates the literature. In 22, we initiates the use of $L_p$ norms for numerical algebraic geometry, with an emphasis on $L_{\infty }$. This classical idea yields strong improvements in the analysis of the number of steps performed by numerous iterative algorithms. In particular, we exhibit three algorithms where, despite the complexity of computing $L_{\infty }$-norm, the use of $L_p$-norms substantially reduces computational complexity: a subdivision-based algorithm in real algebraic geometry for computing the homology of semialgebraic sets, a well-known meshing algorithm in computational geometry, and the computation of zeros of systems of complex quadratic polynomials (a particular case of Smale's 17th problem).

Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces

.

The condition-based complexity analysis framework is one of the gems of modern numerical algebraic geometry and theoretical computer science. One of the challenges that it poses is to expand the currently limited range of random polynomials that we can handle. Despite important recent progress, the available tools cannot handle random sparse polynomials and Gaussian polynomials, that is polynomials whose coefficients are i.i.d. Gaussian random variables. In 30, we initiate a condition-based complexity framework based on the norm of the cube that is a step in this direction. We present this framework for real hypersurfaces and univariate polynomials. We demonstrate its capabilities in two problems, under very mild probabilistic assumptions. On the one hand, we show that the average run-time of the Plantinga-Vegter algorithm is polynomial in the degree for random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. On the other hand, we study the size of the subdivision tree for Descartes' solver and run-time of the solver by Jindal and Sagraloff (2017). In both cases, we provide a bound that is polynomial in the size of the input (size of the support plus logarithm of the degree) for not only on the average, but all higher moments. [This is the journal version of the conference paper with the same title.]

Generalized Perron roots and solvability of the absolute value equation

.

Let A be a real $(n\times n)$-matrix. The piecewise linear equation system $z-A\left|z\right|=b$ is called an absolute value equation (AVE). It is well-known to be equivalent to the linear complementarity problem (LCP). For AVE and LCP unique solvability is comprehensively characterized in terms of conditions on the spectrum (AVE), resp., the principal minors (LCP) of the coefficient matrix. For mere solvability no such characterization exists. In 39, we close this gap in the theory on the AVE-side. The aligning spectrum of A consists of real eigenvalues of the matrices SA, where $S\in diag(+/-n)$, which have a corresponding eigenvector in the positive orthant of Rn. For the mapping degree of the piecewise linear function $z\to z-A\left|z\right|$ we prove, under some mild genericity assumptions on A: The degree is 1 if all aligning values are smaller than 1, it is 0 if all aligning values are larger than 1, and in general it is congruent to (k + 1) mod 2 if k aligning values are larger than 1. The modulus cannot be omitted because the degree can both increase and decrease.

The Multivariate Schwartz–Zippel Lemma

.

Motivated by applications in combinatorial geometry, we consider the following question: Let $\lambda =(\lambda 1,\lambda 2,...,\lambda m)$ be an $m$-partition of a positive integer $n$, $Si\subseteq C\lambda i$ be finite sets, and let $S:=S1\times S2\times ...\times Sm\subset Cn$ be the multi-grid defined by Si. Suppose p is an n-variate degree d polynomial. How many zeros does p have on S? In 28, we first develop a multivariate generalization of the Combinatorial Nullstellensatz that certifies the existence of a point $t\in S$ so that $p\left(t\right)\ne 0$. Then, we show that a natural multivariate generaliza- tion of the DeMillo-Lipton-Schwartz-Zippel lemma holds, except for a special family of polynomials that we call $\lambda$-reducible. This yields a simultaneous generalization of Szemer ́edi-Trotter theorem and Schwartz-Zippel lemma into higher dimensions, and has applications in incidence geometry. Finally, we develop a symbolic algorithm that identifies certain λ-reducible polynomials. More precisely, our symbolic algorithm detects polynomials that include a cartesian product of hypersurfaces in their zero set. It is likely that using Chow forms the algorithm can be generalized to handle arbitrary $\lambda$-reducible polynomials, which we leave as an open problem.

A Geometric Summation of the Geometric Series

.

(read the paper 29, this is a one page contribution).

Coherent presentations of monoids with a right-noetherian Garside family

.

In 24, we show how to construct coherent presentations (presentations by generators, relations and relations among relations) of monoids admitting a right-noetherian Garside family. Thereby, it resolves the question of finding a unifying generalisation of the following two distinct extensions of construction of coherent presentations for spherical Artin-Tits monoids: to general Artin-Tits monoids, and to Garside monoids. The result is applied to some monoids which are neither Artin-Tits nor Garside.

Computation of the $L_{\infty }$-norm of finite-dimensional linear systems

.

In the thesis 43, we study the computation of the $L_{\infty }$-norm of finite-dimensional linear time-invariant systems. This problem is first reduced to the computation of the maximal $y$-projection of the real solutions $(x,y)$ of a bivariate polynomial equations system $\Sigma :\{P=0,\frac{\partial P}{\partial x}=0\}$, where $P\in Z[x,y]$. Then, we use standard computer algebra methods to solve this problem. In particular, we alternatively study a method based on rational univariate representations, a method based on root separation, and finally a method first based on the sign variation of the leading coefficients of a signed subresultant sequence (Sturm-Habicht) and on the identification of an isolating interval for the maximal $y$-projection of the real solutions of $\Sigma$. We then compute the worst-case bit complexity of each method and compare their theoretical behavior. We also implement each method in Maple and compare their practical behavior (average complexity). A generalization of the above algorithms is finally proposed to the case where the polynomial P also depends on a set of parameters $\alpha =[{\alpha }_1,...,{\alpha }_d]\in R^d$. To do that, we solve the problem using the notion of the Cylindrical Algebraic Decomposition, well-known in algebraic geometry.

The Mahler measure of a family of exact polynomials

.

In the thesis 42, we investigate the sequence of Mahler measures of a family of bivariate regular exact polynomials, called $Pd:=P0\le i+j\le dxiyj$ , unbounded in both degree and the genus of the algebraic curve. We obtain a closed formula for the Mahler measure of Pd in termsof special values of the Bloch–Wigner dilogarithm. We approximate $m\left(Pd\right)$, for $1\le d\le 1000$, with arbitrary precision using SageMath. Using 3 different methods we prove that the limitof the sequence of the Mahler measure of this family converges to $9/\left(2{\pi }^2\right)\zeta \left(3\right)$. Moreover, we compute the asymptotic expansion of the Mahler measure of Pd which implies that the rate of the convergence is $O(log\left(d\right)/d^2)$. We also prove a generalization of the theorem of the Boyd-Lawton which asserts that the multivariate Mahler measures can be approximated using the lower dimensional Mahler measures. Finally, we prove that the Mahler measure of Pd, for arbitrary d can be written as a linear combination of L-functions associated with an odd primitive Dirichlet character. In addition, we compute explicitly the representation of the Mahler measure of Pd in terms of $L$-functions, for $1\le d\le 6$.

Structures géométriques et bords des espaces symétriques

.

Dans 41, nous montrons des résultats de complétude et d’incomplétude de certaines variétés fermées portant une structure nil-affine plate, dite à rayons. Ces géométries à rayons apparaissent aux bords des espaces symétriques et dans des contextes variés comme la géométrie affine ou de contact. Nous montrons que les variétés incomplètes ont une développante qui revêt son image. Cela permet de montrer de nouveaux cas de la conjecture de Markus sur les variétés affines fermées à volume parallèle. Nous étudions ensuite les représentations du census de Falbel-Koseleff-Rouillier de groupes fondamentaux de 3-variétés dans le groupe des isométries du plan hyperbolique complexe. Nous proposons le calcul numérique de leurs ensembles limites et désignons ceux qui sont fractals et présentent donc expérimentalement la qualité d’être discret. Nous montrons que les représentations qui semble discrètes grâce à leur ensemble limite se factorisent la plupart du temps par un groupe d’un triangle hyperbolique complexe. Cela généralise un phénomène constaté par Deraux dans un cadre plus large et systématique.

10.1.1 ANR

• ANR JCJC GALOP (Games through the lens of ALgebra and OPptimization)

  Coordinator: Elias Tsigaridas

  Duration: 2018 – 2022

  GALOP is a Young Researchers (JCJC) project with the purpose of extending the limits of the state- of-the-art algebraic tools in computer science, especially in stochastic games. It brings original and innovative algebraic tools, based on symbolic-numeric computing, that exploit the geometry and the structure and complement the state-of-the-art. We support our theoretical tools with a highly efficient open-source software for solving polynomials. Using our algebraic tools we study the geometry of the central curve of (semi-definite) optimization problems. The algebraic tools and our results from the geometry of optimization pave the way to introduce algorithms and precise bounds for stochastic games.

• ANR JCJC SHoCoS (Structure and Homotopy of Configuration Spaces)

  Coordinator: Najib Idrissi (Univ. Paris Cité, IMJ-PRG)

  Participant: Yves Guiraud

  This is a project of fundamental research in mathematics, specifically, algebraic topology, homotopical algebra, and quantum algebra. It is concerned with configuration spaces, which consist in finite sequences of pairwise distinct points in a manifold. Over the past couple of decades, strides have been made in the study and computation of the homotopy types of configuration spaces, i.e., their shape up to continuous deformation. These advances were possible thanks to the rich structure of configuration spaces, which comes from the theory of operads. Moreover, a new theory, factorization homology, allowed the use of configuration spaces to compute topological field theories, topological invariants of manifolds inspired by physics. Our purpose is to exploit the full operadic structure of configuration spaces to obtain new kinds of stabilizations in the homotopy types of configuration spaces, and to use this stability to effectively compute topological field theories from deformation quantization.

10.1.2 Inria Exploratory actions

• LOCUS (non‐Linear geOmetriC compUting at Scale) Inria Exploratory Action

  Coordinator: Elias Tsigaridas

  Duration 2022 - 2025

  Summary : LOCUS shapes a novel theoretical, algorithmic, and computational framework at the intersection of computational algebra, high dimensional geometric and statistical computing, and optimization. It focuses on sampling and integrating in convex bodies, algorithms for convex optimization, and applications in structural biology. It aims to deliver effective theoretical algorithms and efficient open source software for the problems of interest.

• Réal (Réécriture algébrique) Inria Exploratory Action

  Coordinator : Yves Guiraud

  Duration : 2022-2025

  Summary : Rewriting is a branch of computer algebra consisting in transforming mathematical expressions according to admissible rules. Examples range from elementary situations, such as a remarkable identity ${(a+b)}^2=a^2+2ab+b^2$ in a ring, to calculations in complex algebraic structures, such as the Jacobi relation [[x,y],z] = [x,[y,z]] - [[x,z],y] in a Lie algebra.

  The Réal project proposes to explore the connections between rewriting and algebra. The aim is to understand the algebraic foundations of rewriting, to integrate similar calculation mechanisms known in algebra, and to develop new calculation tools with a view to applications in three areas of mathematics: combinatorial and higher algebra, theory groups and representations, study of algebraic systems and varieties.

11.1.1 Scientific events: selection

11.1.2 Journal

11.1.3 Invited talks

• Yves Guiraud gave a talk on Collapsing schemes for differential graded algebras at the Séminaire d'algèbre de l'Institut Camille Jordan, Saint-Étienne, November 2022.
• Antonin Guilloux gave an invited talk on Slimness in the 3-sphere at the conference Complex Hyperbolic Geometry and Related Topics / Autour de la géométrie hyperbolique complexe at Centre International de Rencontres Mathématiques (CIRM).

11.1.4 Scientific expertise

• Yves Guiraud is an elected member of the Comité National de la Recherche Scientifique, section 41 (mathematics), 2021-2026. He is an appointed member of the section bureau.
• Yves Guiraud was an elected member of the Conseil scientifique of the department of mathematics of Univ. Paris Cité, 2019-2022.
• Alban Quadrat was a member of the Scientific Committee of the Journées Nationales de Calcul Formel (JNCF). He is also a member of the technical committee Linear Systems of the International Federation of Automatic Control (IFAC).

11.1.5 Research administration

• Alban Quadrat was a member of the Conseil d'Administration of the Société Mathématique de France (SMF).
• Yves Guiraud is an elected member of the Conseil de laboratoire of IMJ-PRG, since 2021.

11.2.1 Teaching

• Antonin Guilloux, Elias Tsigaridas, Master 1, Effective Linear Algebra and Polynomials. (24h course + 36h exercises)
• Antonin Guilloux, Fabrice Rouillier, Master 1, Introduction to Algebraic geometry (24h course + 36h exercises)
• Jean-Claude Bajard, Antonin Guilloux, Pierre-Vincent Koseleff and Fabrice Rouillier take part to the "agrégation de mathématiques - option C" at Sorbonne Université
• Pierre-Vincent Koseleff : Master 1 Maths - Sorbonne Université : Algebraic Cryptography (36H) at Sorbonne Université
• Pierre-Vincent Koseleff : Master 2 EducFellow in Maths - Computer Algebra (120H) at Sorbonne Université
• Pierre-Vincent Koseleff : Master 1 Maths - Sorbonne Université : Algebraic Algorithmic (36H) at Sorbonne Université
• Pascal Molin manages the Master math-info spécialités crypto et big-data at Paris Université
• Pascal Molin : teaches codes et crypto and théorie de l'information in Master 1 at Paris Université
• Elias Tsigaridas, 24h “Algebraic techniques in optimation”, Master 2 Mathématiques fondamentales, Sorbonne Université.
• Elias Tsigaridas : Algorithms and Competitive Programming, Ingénieur 2A, modal. 20h lectures and 25h TD. Department of Informatics (LIX), École Polytechnique, France
• Elias Tsigaridas : Algorithms for data analysis in C++, Ingénieur 2A. 40h TD. Department of Informatics (LIX), École Polytechnique, France

11.2.2 Supervision

• Jean-Claude Bajard supervises the PhD of Thibauld Feneuil since 10/2020,
• Elias Tsigaridas supervises the PhD of Carles Checa, since 10/2020 (co-supervision with Ioannis Emiris)
• Pierre-Vincent Koseleff supervises the PhD of Andrea Negro , since 10/2021, (co-supervision with Julien Marché IMJ-PRG)
• Elias Tsigaridas and Fabrice Rouillier supervise the PhD of Christina Katsamaki, defense planned in early 2023.
• Yves Guiraud supervises, with Pierre-Louis Curien (CNRS, Univ. Paris Cité, IRIF) the PhD thesis of Alen Đurić. Defence is planned in March 2023
• Alban Quadrat supervises the PhD of Camille Pinto since 10/2022
• Fabrice Rouillier supervises the PhD of Alexandre Lê (Safran CIFRE Grant) (co-dupervision with Damien Chablat - LS2N Nantes)
• Yves Guiraud supervised, with Muriel Livernet (Univ. Paris Cité, IMJ-PRG) the research internship of Filipp Buryak (Ukrainian master student, hosted by Univ. Paris Cité), On the classifying space of Artin monoids (after G. Paolini).
• Yves Guiraud supervised, with Emmanuel Wagner (Univ. Paris Cité, IMJ-PRG) the research internship of Antoine Bussy (M2 mathématiques fondamentales, Sorbonne Université), Diagrammatics for Coxeter groups and their braid groups (after B. Elias and G. Williamson).
• Alban Quadrat supervised the Master thesis of Camille Pinto, Towards an effective integro-differential elimination theory, M2 Algèbre Appliquée, University of Paris Saclay.
• Pierre-Vincent Koseleff supervised Théophile Cartraud with J. -P. Marco, Propriétés et relations entre signaux périodiques et attracteurs nodaux pour la reconstruction de dynamiques complexes, M2 Mathematiques fondamentales, Sorbonne Université.
• Pierre Vicent Koseledd supervised Thibaut Misme Générateurs de l'anneau des entiers d'extensions cyclotomiques réelles, M2 Algèbre Appliquée, University of Paris Saclay.

11.2.3 Juries

• Alban Quadrat was a referee of the PhD thesis of Alexandre Rigaud Analyse des notions de stabilité pour les modèles 2D de Roesser et Fornasini-Marchesini, University of Poitiers, December, 2022.
• Fabrice Rouillier was a referee of the PhD thesis of Owen Rouillé
• Antonin Guilloux and Fabrice Rouillier where in the Jury of the PhD of Mahya Mehrabdollahei 42
• Alban Quadrat en Fabrice Rouillier were in the jury of the PhD of Grace Younes (January 2022)
• Elisah Falbel, Antonin Guilloux and Fabrice Rouillier where in the Jury of the PhD of Raphaël Alexandre, June 2022 41

11.3.1 Internal or external Inria responsibilities

• Yves Guiraud is an elected member of the Comité de centre of the INRIA Research Center of Paris, since 2019 (the committee is inactive since the COVID).

International journals

• 18 articleJ. C.Jean Claude Bajard, K.Kazuhide Fukushima, T.Thomas Plantard and A.Arnaud Sipasseuth. Generating Very Large RNS Bases.IEEE Transactions on Emerging Topics in Computing2022, 1-12
  HALDOIback to text
• 19 articleJ.-C.Jean-Claude Bajard, J.Jérémy Marrez, T.Thomas Plantard and P.Pascal Véron. On Polynomial Modular Number Systems over $/p$.Advances in Mathematics of Communications2022
  HALDOIback to text
• 20 articleR.Razvan Barbulescu and S.Sudarshan Shinde. A classification of ECM-friendly families using modular curves.Mathematics of Computation912022, 1405-1436
  HALDOIback to text
• 21 articleA.Apostolos Chalkis, I. Z.Ioannis Z. Emiris, V.Vissarion Fisikopoulos, P.Panagiotis Repouskos and E.Elias Tsigaridas. Efficient sampling in spectrahedra and volume approximation.Linear Algebra and its Applications648September 2022, 205-232
  HALDOIback to text
• 22 articleF.Felipe Cucker, A. A.Alperen A. Ergür and J.Josué Tonelli-Cueto. Functional norms, condition numbers and numerical algorithms in algebraic geometry.Forum of Mathematics, Sigma10November 2022, e103
  HALDOIback to text
• 23 articleF.Felipe Cucker, A. A.Alperen A. Ergür and J.Josué Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm.Discrete and Computational GeometryAugust 2022
  HALDOIback to text
• 24 articleP.-L.Pierre-Louis Curien, A.Alen Ðurić and Y.Yves Guiraud. Coherent presentations of monoids with a right-noetherian Garside family.Journal of Homotopy and Related Structures2022
  HALback to text
• 25 articleD. N.Daouda Niang Diatta, S.Sény Diatta, F.Fabrice Rouillier, M.-F.Marie-Françoise Roy and M.Michael Sagraloff. Bounds for polynomials on algebraic numbers and application to curve topology.Discrete and Computational Geometry67February 2022, 631–697
  HALDOIback to textback to textback to textback to text
• 26 articleA.Antoine Joux and C.Cécile Pierrot. Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms.Advances in Mathematics of Communications2022
  HALback to text
• 27 articleC.Christina Katsamaki, F.Fabrice Rouillier, E.Elias Tsigaridas and Z.Zafeirakis Zafeirakopoulos. PTOPO: Computing the Geometry and the Topology of Parametric Curves.Journal of Symbolic ComputationAugust 2022
  HALDOIback to text
• 28 articleM.Mahmut Levent Doğan, A.Alperen Ergür, J.Jake Mundo and E.Elias Tsigaridas. The Multivariate Schwartz--Zippel Lemma.SIAM Journal on Discrete Mathematics362June 2022, 888-910
  HALDOIback to text
• 29 articleJ.Josué Tonelli-Cueto. A Geometric Summation of the Geometric Series.The American Mathematical MonthlySeptember 2022, 1-1
  HALDOIback to textback to text
• 30 articleJ.Josué Tonelli-Cueto and E.Elias Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces.Journal of Symbolic Computation1152022, 142-173
  HALDOIback to text

International peer-reviewed conferences

• 31 inproceedingsA.Apostolos Chalkis, C.Christina Katsamaki and J.Josué Tonelli-Cueto. On the Error of Random Sampling: Uniformly Distributed Random Points on Parametric Curves.ISSAC '22 - International Symposium on Symbolic and Algebraic ComputationVilleneuve-d'Ascq, FranceJuly 2022
  HALDOIback to text
• 32 inproceedingsC.Cyrille Chenavier, T.Thomas Cluzeau and A.Alban Quadrat. Computation of Koszul homology and application to involutivity of partial differential systems.SSSC 2022 - 8th IFAC Symposium on System Structure and ControlMontréal, CanadaSeptember 2022
  HALback to text
• 33 inproceedingsA. A.Alperen A. Ergür, J.Josué Tonelli-Cueto and E.Elias Tsigaridas. Beyond Worst-Case Analysis for Root Isolation Algorithms.ISSAC '22 - International Symposium on Symbolic and Algebraic ComputationVilleneuve-d'Ascq, FranceJuly 2022
  HALback to text
• 34 inproceedingsT.Thibauld Feneuil, J.Jules Maire, M.Matthieu Rivain and D.Damien Vergnaud. Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection.Advances in Cryptology - Asiacrypt 2022ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security13792Lecture Notes in Computer ScienceTaipei, TaiwanSpringer2022, 1-32
  HALDOIback to text
• 35 inproceedingsP.Pascal Molin and A.Aurel Page. Computing groups of Hecke characters.ANTS-XV 2022 - Fifteenth Algorithmic Number Theory SymposiumBristol, United KingdomOctober 2022
  HALback to textback to text
• 36 inproceedingsA.Alban Quadrat. An Integro-differential Operator Approach to Linear State-space Systems.SSSC 2022 - 8th IFAC Symposium on System Structure and ControlMontreal, CanadaSeptember 2022
  HALDOIback to text
• 37 inproceedingsA.Alban Quadrat. An Integro-differential-delay Operator Approach to Transformations of Linear Differential Time-delay Systems.SSSC 2022 - 8th IFAC Symposium on System Structure and ControlMontréal, CanadaSeptember 2022
  HALDOIback to text
• 38 inproceedingsA.Alban Quadrat. An integro-differential operator approach to linear differential systems.MTNS 2022 - 25th International Symposium on Mathematical Theory of Networks and SystemsBayreuth, GermanySeptember 2022
  HALDOIback to text
• 39 inproceedingsM.Manuel Radons and J.Josué Tonelli-Cueto. Generalized Perron roots and solvability of the absolute value equation.Discrete Mathematics Days 2022Santander, SpainEditorial Universidad de CantabriaJuly 2022, 237-242
  HALDOIback to text

Scientific book chapters

• 40 inbookA.Alban Quadrat and R.Rosane Ushirobira. On the Ore extension ring of differential time-varying delay operators.ADD-2Accounting for Constraints in Delay Systems, Advances in Delays and Dynamics (ADD), volume 12, Springer, pp. 87-107Advances in Delays and DynamicsSpringerApril 2022, pp. 87-107
  HALDOIback to text

Doctoral dissertations and habilitation theses

• 41 thesisR. V.Raphaël V Alexandre. Geometric structures and boundaries of symmetric spaces.Sorbonne UniversitéJune 2022
  HALback to textback to text
• 42 thesisM.Mahya Mehrabdollahei. The Mahler measure of a family of exact polynomials.Sorbonne UniversitéJuly 2022
  HALback to textback to text
• 43 thesisG.Grace Younes. Computation of the L∞-norm of finite-dimensional linear systems.Sorbonne UniversitéJanuary 2022
  HALback to text

Reports & preprints

• 44 miscF.François Brunault, A.Antonin Guilloux, M.Mahya Mehrabdollahei and R.Riccardo Pengo. Limits of Mahler measures in multiple variables.March 2022
  HALback to text
• 45 miscE.Elisha Falbel, A.Antonin Guilloux and P.Pierre Will. Slim curves, limit sets and spherical CR uniformisations.May 2022
  HALback to text
• 46 miscK.Khazhgali Kozhasov and J.Josué Tonelli-Cueto. Probabilistic bounds on best rank-one approximation ratio.January 2022
  HAL
• 47 miscM.Manuel Radons and J.Josué Tonelli-Cueto. Generalized Perron Roots and Solvability of the Absolute Value Equation.June 2022
  HAL
• 48 miscJ.Josué Tonelli-Cueto. A $p$-adic Descartes solver: the Strassman solver.March 2022
  HAL

Other scientific publications

• 49 inproceedingsJ. G.Jazz G. Suchen and J.Josué Tonelli-Cueto. Ultrametric Smale's α-theory.International Symposium on Symbolic and Algebraic Computation562Lille, FranceJune 2022, 56–59
  HALDOI