Welcome

BS-small 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

tore-cycles 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]. circuit100
exc100 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]. probaquad
  1. A. Bostan, P. Lairez, and B. Salvy, “Creative telescoping for rational functions using the Griffiths-Dwork method,” in Issac ’13: proceedings of the 38th international symposium on symbolic and algebraic computation, 2013, pp. 93-100.
    arXiv:abs/1301.4313
    doi:10.1145/2465506.2465935
    [BibTeX] [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.

    @inproceedings{BostanLairezSalvy2013,
    Arxiv = {abs/1301.4313},
    Author = {Bostan, Alin and Lairez, Pierre and Salvy, Bruno},
    Booktitle = {ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation},
    Date-Added = {2013-07-02 11:35:49 +0000},
    Date-Modified = {2013-07-02 11:35:49 +0000},
    Doi = {10.1145/2465506.2465935},
    Editor = {Kauers, Manuel},
    Eprint = {1301.4313},
    Pages = {93--100},
    Publisher = {ACM Press},
    Title = {Creative telescoping for rational functions using the {G}riffiths-{D}work method},
    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.
    },
    Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDxJXTlMua2V5c1pOUy5vYmplY3RzViRjbGFzc6INDoACgAOiEBGABIAFgAdccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QXC4uLy4uLy4uLy4uLy4uLy4uLy4uLy4uLy4uL1VzZXJzL3NhbHZ5L0dvb2dsZSBEcml2ZS9CaWJsaW8vYXJ0aWNsZS9Cb3N0YW5MYWlyZXpTYWx2eTIwMTMucGRm0hcLGBlXTlMuZGF0YU8RAdYAAAAAAdYAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMf841NIKwAAALC1VxlCb3N0YW5MYWlyZXpTYWx2eTIwMTMucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABLevKzWUPbQAAAAAAAAAAAAoABgAACSAAAAAAAAAAAAAAAAAAAAAHYXJ0aWNsZQAAEAAIAADH/MczAAAAEQAIAADNZQFdAAAAAQAUALC1VwCyNyAAsjbnACcergAAk1MAAgBTTWFjaW50b3NoIEhEOlVzZXJzOgBzYWx2eToAR29vZ2xlIERyaXZlOgBCaWJsaW86AGFydGljbGU6AEJvc3RhbkxhaXJlelNhbHZ5MjAxMy5wZGYAAA4ANAAZAEIAbwBzAHQAYQBuAEwAYQBpAHIAZQB6AFMAYQBsAHYAeQAyADAAMQAzAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBBVXNlcnMvc2FsdnkvR29vZ2xlIERyaXZlL0JpYmxpby9hcnRpY2xlL0Jvc3RhbkxhaXJlelNhbHZ5MjAxMy5wZGYAABMAAS8AABUAAgAM//8AAIAG0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVQBgAGcAagBsAG4AcQBzAHUAdwCEAI4A7QDyAPoC1ALWAtsC5gLvAv0DAQMIAxEDFgMjAyYDOAM7A0AAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADQg==},
    Bdsk-Url-1 = {http://arxiv.org/abs/1301.4313}}

  2. C. Pivoteau, B. Salvy, and M. Soria, “Algorithms for combinatorial structures: well-founded systems and Newton iterations,” Journal of combinatorial theory, series a, vol. 119, pp. 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,
    Arxiv = {abs/1109.2688},
    Author = {Pivoteau, Carine and Salvy, Bruno and Soria, Mich{\`e}le},
    Doi = {10.1016/j.jcta.2012.05.007},
    Journal = {Journal of Combinatorial Theory, Series A},
    Pages = {1711--1773},
    Title = {Algorithms for Combinatorial Structures: Well-founded systems and {N}ewton iterations},
    Volume = {119},
    Year = {2012},
    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.},
    Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.jcta.2012.05.007}}

  3. A. Bostan, K. Raschel, and B. Salvy, “Non-D-finite excursions in the quarter plane,” Journal of combinatorial theory, series a, vol. 121, pp. 45-63, 2014.
    arXiv:abs/1205.3300
    doi:10.1016/j.jcta.2013.09.005
    [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$.

    @article{BostanRaschelSalvy2014,
    Arxiv = {abs/1205.3300},
    Author = {Bostan, Alin and Raschel, Kilian and Salvy, Bruno},
    Date-Added = {2013-10-04 14:03:46 +0000},
    Date-Modified = {2013-10-04 14:04:09 +0000},
    Doi = {10.1016/j.jcta.2013.09.005},
    Eprint = {1205.3300},
    Institution = {arXiv},
    Journal = {Journal of Combinatorial Theory, Series A},
    Pages = {45--63},
    Title = {Non-{D}-finite excursions in the quarter plane},
    Volume = {121},
    Year = {2014},
    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$.
    }}

  4. M. Bardet, J. Faugère, B. Salvy, and P. Spaenlehauer, “On the complexity of solving quadratic boolean systems,” Journal of complexity, vol. 29, iss. 1, pp. 53-75, 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,
    Arxiv = {abs/1112.6263},
    Author = {Bardet, Magali and Faug{\`e}re, Jean-Charles and Salvy, Bruno and Spaenlehauer, Pierre-Jean},
    Doi = {10.1016/j.jco.2012.07.001},
    Journal = {Journal of Complexity},
    Month = {f{\'e}vrier},
    Number = {1},
    Pages = {53--75},
    Title = {On the Complexity of Solving Quadratic Boolean Systems},
    Volume = {29},
    Year = {2013},
    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.
    },
    Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.jco.2012.07.001}}

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


Address

LIP – ENS Lyon
46, allée d’Italie
69364 Lyon Cedex 07
France

email: Firstname.Lastname@inria.fr
phone: (+33) (0)4 37 28 76 23

Visitors

My office is #274
on the 2nd floor of the LUG.
Here are directions to get there.

 

Call me if you cannot get inside the building.