Bruno Salvy's Home Page

I’m an Inria researcher in  the AriC project, which is part of the LIP lab in ENS Lyon. I recently moved there after more than 20 years in the stimulating environment of the Algorithms project in Rocquencourt (near Paris). My field of research is computer algebra. It is the study of effective mathematics and their complexity: how much mathematics can be done by a computer, and how fast? In this area, I am mostly interested in applications to classical analysis (asymptotics, special functions) and combinatorics. See the menus “Software” and “Publications” for more information.

Recent Work

Definite integrals of rational functions in several variables provide elementary representations for a large number of special functions, or combinatorial sequences through their generating functions. These integrals satisfy linear differential equations from which a lot of information about them can be extracted easily. The computation of these integrals is a classical topic, going back at least to Émile Picard, with recent progress based on creative telescoping. See [1] for more.

A combinatorial version of Newton’s iteration leads to fast routines for the enumeration and random generation of series-parallel graphs. This is just an example of a very general approach to a large family of combinatorial structures that can be defined recursively [2].

This is a walk of 100 steps in the quarter plane, starting at the origin, using only steps N,S,E,W,SE, and ending at the origin. The number of such walks (called excursions) of length n does not satisfy a linear recurrence with polynomial coefficients, while it does for other step sets. A computer-aided proof of this and related facts relies on probability theory (eigenvalues of a Laplacian); number theory (G-functions); and an irrationality result. See [3] for more.

The behaviour of quadratic boolean systems is very regular and can be predicted rather precisely. This is the basis of an efficient algorithm that solves them. See [4].

• Alin Bostan, Pierre Lairez, and Bruno Salvy. — Creative telescoping for rational functions using the Griffiths-Dwork method. — Issac ’13, 2013.
  arXiv:abs/1301.4313
  [BibTeX] [Abstract] [Download PDF]
  

  Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths–Dwork method for the creative telescoping of rational functions. This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is simply exponential in the number of variables. One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.

  @inproceedings{BostanLairezSalvy2013,
  Arxiv = {abs/1301.4313},
  Author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
  Booktitle = {ISSAC '13},
  Date-Added = {2013-03-12 15:59:09 +0000},
  Date-Modified = {2013-04-26 13:55:52 +0000},
  Eprint = {1301.4313},
  Title = {Creative telescoping for rational functions using the {G}riffiths-{D}work method},
  Url = {http://arxiv.org/abs/1301.4313},
  Year = {2013},
  Abstract = {Creative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters.
  We describe a precise and elementary algorithmic version of the Griffiths--Dwork method for the creative telescoping of rational functions.
  This leads to bounds on the order and degree of the coefficients of the differential equation, and to the first complexity result which is simply exponential in the number of variables.
  One of the important features of the algorithm is that it does not need to compute certificates. The approach is vindicated by a prototype implementation.
  },
  }

• Carine Pivoteau, Bruno Salvy, and Michèle Soria. — Algorithms for combinatorial structures: well-founded systems and Newton iterations. — Journal of Combinatorial Theory, Series A, 119 1711-1773, 2012.
  arXiv:abs/1109.2688
  doi:10.1016/j.jcta.2012.05.007
  [BibTeX] [Abstract]
  

  We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing numerical values. Our framework is an articulation of the constructible classes of Flajolet and Sedgewick with Joyal’s species theory. We extend the implicit species theorem to structures of size zero. A quadratic iterative Newton method is shown to solve well-founded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasi-optimal complexity. This iteration transfers to a numerical scheme that converges unconditionally to the values of the generating series inside their disk of convergence. These results provide important subroutines in random generation. Finally, the approach is extended to combinatorial differential systems.

  @article{PivoteauSalvySoria2012,
  Author = {Pivoteau, Carine and Salvy, Bruno and Soria, Michèle},
  Title = {Algorithms for Combinatorial Structures: Well-founded systems and {N}ewton iterations},
  Journal = {Journal of Combinatorial Theory, Series A},
  Year = {2012},
  Volume = {119},
  Pages = {1711--1773},
  Doi = {10.1016/j.jcta.2012.05.007},
  Abstract = {We consider systems of recursively defined combinatorial structures. We give algorithms checking that these systems are well founded, computing generating series and providing numerical values. Our framework is an articulation of the constructible classes of Flajolet and Sedgewick with Joyal's species theory. We extend the implicit species theorem to structures of size zero. A quadratic iterative Newton method is shown to solve well-founded systems combinatorially. From there, truncations of the corresponding generating series are obtained in quasi-optimal complexity. This iteration transfers to a numerical scheme that converges unconditionally to the values of the generating series inside their disk of convergence. These results provide important subroutines in random generation. Finally, the approach is extended to combinatorial differential systems.},
  Arxiv = {abs/1109.2688},
  }

• Alin Bostan, Kilian Raschel, and Bruno Salvy. — Non-D-finite excursions in the quarter plane. — arXiv, 1205.3300, 2012.
  arXiv:abs/1205.3300
  [BibTeX] [Abstract]
  

  We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$ of excursions in the quarter plane corresponding to a nonsingular step set $\mathfrak{S}\subseteq\{0,\pm 1\}^2$ with infinite group does not satisfy any nontrivial linear recurrence with polynomial coefficients. Accordingly, in those cases, the trivariate generating function of the numbers of walks with given length and prescribed ending point is not D-finite. Moreover, we display the asymptotics of $e^{\mathfrak{S}}_n$.

  @techreport{BostanRaschelSalvy2012,
  Author = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
  Title = {Non-{D}-finite excursions in the quarter plane},
  Institution = {arXiv},
  Year = {2012},
  Abstract = {We prove that the sequence $(e^{\mathfrak{S}}_n)_{n\geq 0}$ of excursions in the quarter plane corresponding to a nonsingular step set $\mathfrak{S}\subseteq\{0,\pm 1\}^2$ with infinite group does not satisfy any nontrivial linear recurrence with polynomial coefficients. Accordingly, in those cases, the trivariate generating function of the numbers of walks with given length and prescribed ending point is not D-finite. Moreover, we display the asymptotics of $e^{\mathfrak{S}}_n$.},
  Number = {1205.3300},
  Arxiv = {abs/1205.3300},
  }

• Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Pierre-Jean Spaenlehauer. — On the complexity of solving quadratic boolean systems. — Journal of Complexity, 29.1:53-75, février 2013.
  arXiv:abs/1112.6263
  doi:10.1016/j.jco.2012.07.001
  [BibTeX] [Abstract]
  

  A fundamental problem in computer science is to find all the common zeroes of $m$ quadratic polynomials in $n$ unknowns over ${F}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in $4\log_2 n\,2^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step. Under precise algebraic assumptions, we show that the deterministic variant of our algorithm has complexity bounded by $O(2^{0.841n})$ when $m=n$, while a probabilistic variant of the Las Vegas type has expected complexity $O(2^{0.792n})$. Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to~1. We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as~200, and thus very relevant for cryptographic applications.

  @article{BardetFaugereSalvySpaenlehauer2013,
  Author = {Bardet, Magali and Faugère, Jean-Charles and Salvy, Bruno and Spaenlehauer, Pierre-Jean},
  Title = {On the Complexity of Solving Quadratic Boolean Systems},
  Journal = {Journal of Complexity},
  Year = {2013},
  Volume = {29},
  Number = {1},
  Pages = {53--75},
  Month = {février},
  Doi = {10.1016/j.jco.2012.07.001},
  Abstract = {A fundamental problem in computer science is to find all the common zeroes of $m$ quadratic polynomials in $n$ unknowns over ${F}_2$. The cryptanalysis of several modern ciphers reduces to this problem. Up to now, the best complexity bound was reached by an exhaustive search in $4\log_2 n\,2^n$ operations. We give an algorithm that reduces the problem to a combination of exhaustive search and sparse linear algebra. This algorithm has several variants depending on the method used for the linear algebra step.
  Under precise algebraic assumptions, we show that the deterministic variant of our algorithm has complexity bounded by $O(2^{0.841n})$ when $m=n$, while a probabilistic variant of the Las Vegas type has expected complexity $O(2^{0.792n})$.
  Experiments on random systems show that the algebraic assumptions are satisfied with probability very close to~1.
  We also give a rough estimate for the actual threshold between our method and exhaustive search, which is as low as~200, and thus very relevant for cryptographic applications.
  },
  Arxiv = {abs/1112.6263},
  }

The full collection of my recent (and not so recent) papers is here.