Éric Schost (original) (raw)

• Bit complexity for computing one point in each connected component of a smooth real algebraic set, with J. Elliott and M. Giesbrecht.
  Journal of Symbolic Computation, to appear.
  PDF.
• Subquadratic-time algorithms for normal bases, with M. Giesbrecht and A. Jamshidpey.
  Computational Complexity, 30(5), 2021.
  PDF.
• Solving determinantal systems using homotopy techniques, with J. D. Hauenstein, M. Safey El Din and T. X. Vu.
  Journal of Symbolic Computation, 104:754-804, 2021.
  PDF.
• Homotopy techniques for solving sparse column support determinantal polynomial systems, with G. Labahn, M. Safey El Din and T. X. Vu.
  Journal of Complexity 66, 2021.
  PDF.
• Sparse multiplication of multivariate linear differential operators, with M. Giesbrecht and Q. Huang.
  Proceedings ISSAC’21, pp. 155–162, 2021.
  PDF.
• Algorithms for linearly recurrent sequences of truncated polynomials, with S. G. Hyun and V. Neiger.
  Proceedings ISSAC’21, pp. 201–208, 2021.
  PDF.
• Computing syzygies in finite dimension using fast linear algebra, with V. Neiger.
  Journal of Complexity, 60, 2020.
  PDF.
• On the bit complexity of finding points in connected components of a smooth real hypersurface, with J. Elliott and M. Giesbrecht.
  Proceedings ISSAC’20, pp. 170–177, 2020.
  PDF.
• Sparse multiplication for skew polynomials, with M. Giesbrecht and Q. Huang.
  Proceedings ISSAC’20, pp. 194–201, 2020.
  PDF.
• Block-Krylov techniques in the context of sparse-FGLM algorithms, with K. Hyun, V. Neiger and H. Rahkooy.
  Journal of Symbolic Computation, 98:163-191, 2019.
  PDF.
• Computing isomorphisms and embeddings of finite fields, with L. Brieulle, L. De Feo, J. Doliskani and J.-P. Flori.
  Mathematics of Computation, 88(317): 1391-1426, 2019.
  PDF.
• Quadratic-time algorithms for normal elements, with A. Jamshidpey and M. Giesbrecht.
  Proceedings ISSAC’19, pp. 179–186, 2019.
  PDF.
• Change of basis for m-primary ideals in one and two variables, with K. Hyun, S. Melczer and C. St-Pierre.
  Proceedings ISSAC’19, pp. 227–234, 2019.
  PDF.
• Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants, with K. Hyun and V. Neiger.
  Proceedings ISSAC’19, pp. 235–242, 2019.
  PDF.
• Computing the characteristic polynomial of a finite rank two Drinfeld module, with Y. Musleh.
  Proceedings ISSAC’19, pp. 307–314, 2019.
  PDF.
• Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, with J. Doliskani and A. Narayanan.
  Journal of Symbolic Computation, 105:199-213, 2018.
  PDF.
• Algebraic construction of quasi-split algebraic tori, with A. Jamshidpey and N. Lemire.
  Journal of Algebra and its Applications, 19(11), 2018.
  PDF.
• Bit complexity for multi-homogeneous polynomial system solving - application to polynomial minimization, with M. Safey El Din.
  Journal of Symbolic Computation, 87: 176-206, 2018.
  PDF.
• On semiring complexity of Schur polynomials, with S. Fomin, D. Grigoriev and D. Nogneng.
  Computational Complexity, 27(4): 595-616, 2018.
  PDF.
• _On the evaluation of some sparse polynomials,_with D. Nogneng.
  Mathematics of Computation, 87(310): 893-904, 2018.
  PDF.
• _On matrices with displacement structure: generalized operators and faster algorithms,_with A. Bostan, C.-P. Jeannerod and C. Mouilleron.
  SIAM Journal on Matrix Analysis and Applications, 38(3): 733-775, 2017.
  PDF.
• _Computing minimal interpolation bases,_with C.-P. Jeannerod, V. Neiger and G. Villard.
  Journal of Symbolic Computation, 83: 272-314, 2017.
  PDF.

_A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets,_with M. Safey El Din.
Journal of the ACM 63(6):1-48, 2017.
PDF

• Algorithms for structured linear systems solving and their implementation, with K. Hyun and R. Lebreton.
  Proceedings ISSAC’17, pp. 205–212, 2017.
  PDF.
• Sparse rational univariate representation, with A. Mantzaflaris and E. Tsigaridas.
  Proceedings ISSAC’17, pp. 301–308, 2017.
  PDF.
• Algorithms for zero-dimensional ideals using linear recurrent sequences, with V. Neiger and H. Rahkooy.
  Proceedings CASC’17, pp. 313–328, 2017.
  PDF.
• Fast computation of roots of polynomials over the ring of power series, with V. Neiger and J. Rosenkilde.
  Proceedings ISSAC’17, pp. 349–356, 2017.
  PDF.
• _Explicit isogenies in quadratic time in any characteristic,_with C. Hugounenq, L. De Feo and J. Plˆut.
  LMS Journal of Computation and Mathematics 19 (A), pp. 267-282, 2016
  PDF.
• Computation of the similarity class of the p-curvature, with X. Caruso and A. Bostan
  Proceedings ISSAC'16, pp. 111-118, 2016.
  PDF.
• _Fast computation of minimal interpolation bases in Popov form for arbitrary shifts,_with C.-P. Jeannerod, V. Neiger and G. Villard.
  Proceedings ISSAC'16: 295-302, 2016
  PDF.
• A fast algorithm for computing the truncated resultant, with G. Moroz
  Proceedings ISSAC'16, pp. 341-348, 2016.
  PDF.
• A quasi-optimal Monte Carlo algorithm for the symbolic solution of polynomial systems in Z[X,Y], with E. Mehrabi.
  Journal of Complexity 34:78-128, 2016.
  PDF.
• A simple and fast online power series multiplication and its analysis, with R. Lebreton
  Journal of Symbolic Computation, 72: 231-251, 2016.
  PDF.
• A quadratically convergent algorithm for structured low-rank approximation, with P.-J. Spaenlehauer
  Foundations of Computational Mathematics, 16(2): 457-492, 2016.
  PDF.
• Algorithms for finite field arithmetic.
  Proceedings ISSAC'15, pp. 7-15, 2015 (invited).
  PDF.
• A fast algorithm for computing the p-curvature, with X. Caruso and A. Bostan
  Proceedings ISSAC'15, pp. 69-76, 2015.
  PDF.
• _Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations,_with M. Chowdhury, C.-P. Jeannerod, V. Neiger and G. Villard.
  IEEE Transactions on Information Theory, 61(5):2370-2387, 2015.
  PDF.
• A standard basis free algorithm for computing the tangent cones of a space curve, with P. Alvandi, M. Moreno Maza and P. Vrbik.
  Proceedings CASC'15, pp. 45-60, 2015.
  PDF.
• Computing in degree 2^k-extensions of finite fields of odd characteristic, with J. Doliskani
  Design, codes and cryptography 74: 559-569, 2015.
  PDF.
• Doing algebraic geometry with the RegularChains library, with P. Alvandi, C. Chen, S. Marcus, M. Moreno Maza and P. Vrbik.
  ICMS'14, pp. 472-479, Springer, 2014.
  PDF.
• A fast algorithm for computing the characteristic polynomial of the p-curvature, with X. Caruso and A. Bostan
  Proceedings ISSAC'14, pp. 59-66, ACM, 2014.
  PDF.
• Fast arithmetic for the algebraic closure of finite fields, with L. De Feo, J. Doliskani
  Proceedings ISSAC'14, pp. 122-129, ACM, 2014.
  PDF.
• On the complexity of solving bivariate systems: the case of non-singular solutions, with R. Lebreton, E. Mehrabi
  Proceedings ISSAC'13, pp. 251-258, ACM, 2013.
  PDF.
• Structured FFT and TFT: symmetric and lattice polynomials, with J. van der Hoeven, R. Lebreton
  Proceedings ISSAC'13, pp. 355-362, ACM, 2013.
  PDF.
• Fast algorithms for l-adic towers over finite fields, with L. De Feo, J. Doliskani
  Proceedings ISSAC'13, pp. 165-172, ACM, 2013.
  PDF.
• A baby step-giant step roadmap algorithm for general algebraic sets, with S. Basu, M.-F. Roy, M. Safey El Din
  Foundations of Computational Mathematics, 14: 1117-1172, 2014.
  PDF.
• Algorithms for the universal decomposition algebra, with R. Lebreton
  Proceedings ISSAC'12, pp. 234-241, ACM, 2012.
  PDF.
• Power series solutions of singular (q)-differential equations, with A. Bostan, M. F. I. Chowdhury, R. Lebreton and B. Salvy
  Proceedings ISSAC'12, pp. 107-114, ACM, 2012.
  PDF.
• Inversion modulo zero-dimensional regular chains, with M. Moreno Maza and P. Vrbik
  Proceedings CASC'12, pp. 224-235, Springer, 2012.
  PDF.
• On the complexity of computing with zero-dimensional triangular sets, with A. Poteaux
  Journal of Symbolic Computation 50: 110-138, 2013.
  PDF.
• Modular composition modulo triangular sets and applications, with A. Poteaux
  Computational Complexity 22: 463-516, 2013.
  PDF.
• Taking roots over high extensions of finite fields, with J. Doliskani
  Mathematics of Computation 83: 435-446, 2014.
  PDF.
• Genus 2 point counting over prime fields, with P. Gaudry
  Journal of Symbolic Computation 47 (4): 368-400, 2012.
  PDF.
• Multipoint evaluation in higher dimensions, with J. van der Hoeven
  Applicable Algebra in Engineering, Communication and Computing 24 (1): 37-52, 2013.
  PDF.
• Bit-size estimates for triangular sets in positive dimension, with A. Kadri and X. Dahan
  Journal of Complexity 28(1), 109-135, 2012.
  PDF.
• Optimization techniques for small matrix multiplication, with C.-É. Drevet and Md. N. Islam
  Theoretical Computer Science 412(22), 2219-2236, 2011.
  PDF.
• Transalpyne: a language for automatic transposition, with L. De Feo
  Communications in Computer Algebra 44 (3/4), 2010.
  PDF.
• The mopdn library: bringing fast polynomial arithmetic into Maple, with X. Li and M. Moreno Maza and R. Rasheed
  Journal of Symbolic Computation 46 (7), 841-858, 2011.
  PDF.
• Homotopy methods for multiplication modulo triangular sets, with A. Bostan, M. F. I. Chowdhury, J. van der Hoeven.
  Journal of Symbolic Computation 46 (12), 1378-1402, 2011.
  PDF.
• Analytical solution of the tooling/workpiece contact interface shape during a flow forming operation, with M. J. Roy, D. M. Maijera, R. J. Klassen, J. T. Wood.
  Journal of Materials Processing Technology 210 (14), 1976-1985, 2010.
  PDF.
• A baby steps/giant steps probabilistic algorithm for computing roadmaps in smooth bounded real hypersurface, with M. Safey El Din.
  Discrete and Computational Geometry 45 (1), 181-220, 2011.
  PDF.
• On the geometry of polar varieties, with B. Bank, M. Giusti, J. Heintz, M. Safey El Din.
  Applicable Algebra in Engineering, Communication and Computing 21(1), 33-83, 2010.
  PDF.
• Code generation for polynomial multiplication, with L. Ding.
  Proceedings CASC'09, pp. 66-78, Springer, 2009.
  PDF.
• Interpolation of polynomials given by straight-line programs, with S. Garg.
  Theoretical Computer Science, 410(27-29), 2659-2662, 2009.
  PDF.
• A simple and fast algorithm for computing exponentials of power series, with A. Bostan.
  Information Processing Letters 109(13), 754-756, 2009.
  PDF.
• Fast algorithms for differential equations in positive characteristic, with A. Bostan.
  Proceedings ISSAC'09, pp. 47-54, ACM Press, 2009.
  PDF.
• Fast arithmetics in Artin-Schreier towers over finite fields, with L. De Feo
  Proceedings ISSAC'09, pp. 127-134, ACM Press, 2009.
  PDF.
  Journal version, Journal of Symbolic Computation, to appear.
  PDF.
• Evaluation properties of invariant polynomials, with X. Dahan, J. Wu.
  Journal of Symbolic Computation, 44(11): 1592-1604.
  PDF.
• Trinomial bases and Chinese remaindering for modular polynomial multiplication, with A. Hariri.
  Proceedings SAC'08, pp. 361-372, Springer, 2009.
  PDF.
• High-performance symbolic computation in a hybrid compiled-interpreted programming environment, with X. Li, M. Moreno Maza, R. Rasheed.
  Proceedings ICCSA'08, pp. 331-341, IEEE, 2008.
  PDF.
• Fast conversion algorithms for orthogonal polynomials, with A. Bostan, B. Salvy.
  Linear Algebra and its Applications 432(1): 249-258, 2010.
  PDF.
• Power series composition and change of basis, with A. Bostan, B. Salvy.
  Proceedings ISSAC'08, pp. 269-276, ACM Press, 2008.
  PDF.
• Change of order for regular chains in positive dimension, with X. Dahan, X. Jin, M. Moreno Maza.
  Theoretical Computer Science 392(1-3): 37-65, 2008.
  PDF,PS.
• Fast algorithms for computing isogenies between elliptic curves, with A. Bostan, F. Morain, B. Salvy.
  Mathematics of Computation 77: 1755-1778, 2008.
  PDF,PS.
• Modular equations for hyperelliptic curves, with P. Gaudry.
  Mathematics of Computation 74: 429-454, 2007.
  PS, PDF, DVI.
  The modular equation for 3-torsion defined there.
• Differential equations for algebraic functions, with A. Bostan, F. Chyzak, G. Lecerf, B. Salvy.
  Proceedings ISSAC'07, pp. 25-32, ACM Press, 2007.
  PDF.
• Computing the eigenvalue in the Schoof-Elkies-Atkin algorithm using Abelian lifts, with F. Morain, P. Mihailescu.
  Proceedings ISSAC'07, pp 285-292, ACM Press, 2007.
  PDF,PS.
• Fast Arithmetic for triangular sets: from theory to practice, with X. Li, M. Moreno Maza.
  Proceedings ISSAC'07, pp. 269-276, ACM Press 2007.
  PDF,PS.
  Journal version, Journal of Symbolic Computation 44(7):891-907
  PDF.
• Solving Toeplitz- and Vandermonde-like linear systems with large displacement rank, with A. Bostan, C.-P. Jeannerod.
  Proceedings ISSAC'07, pp. 33-40, ACM Press, 2007.
  PDF,PS.
  Solving structured linear systems with large displacement rank, journal version.
  Theoretical Computer Science 407(1-3): 155-18, 2008.
  PDF,PS.
• Fast computation of power series solutions of systems of differential equations, with A. Bostan, F. Chyzak, F. Ollivier, B. Salvy, A. Sedoglavic.
  Proceedings SODA'07, pp. 1012-1021, SIAM, 2007.
  PDF,PS.
• Change of order for bivariate triangular sets, with C. Pascal.
  Proceedings ISSAC'06, pp. 277-284, ACM Press, 2006.
  PDF,PS.
• Implementation techniques for fast polynomial arithmetic in a high-level programming environment, with A. Filatei, M. Moreno Maza, X. Li.
  Proceedings ISSAC'06, pp. 93-100, ACM Press, 2006.
  PDF,PS.
• Primary decomposition of zero-dimensional ideals: Putting Monico's algorithm into practice (extended abstract), with M. Moreno Maza, W. Zhou.
  Transgressive Computing.
  PDF,PS.
• On the complexity of the D5 principle, with X. Dahan, M. Moreno Maza, Y. Xie.
  Transgressive Computing.
  PDF,PS.
• There is no reverse derivation mode for discrete derivatives.
  Theoretical Computer Science 347(1-2): 299-305, 2005.
  PDF,PS.
• _Lifting techniques for triangular decompositions,_with X. Dahan, M. Moreno Maza, W. Wu, Y. Xie.
  Proceedings ISSAC'05, pp. 108-115, ACM Press, 2005.
  PDF.
• Multivariate power series multiplication.
  Proceedings ISSAC'05, pp. 293-300, ACM Press, 2005.
  PDF,PS.
• Evaluation properties of symmetric polynomials, with P. Gaudry et N. Thiéry.
  International Journal of Algebra and Computation 16(3): 505-524, 2006.
  PDF,PS.
• On the complexities of multipoint evaluation and interpolation, with A. Bostan.
  Theoretical Computer Science 329(1-3): 223-235, 2004.
  PDF,PS.
• A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm, with P. Gaudry.
  Proceedings ANTS 6, pp. 208-222, Springer, 2006.
  PDF,PS.
• Sharp estimates for triangular sets, with X. Dahan.
  Proceedings ISSAC'04, pp. 103-110, ACM Press, 2004.
  PDF,PS.
• Complexity Issues in Bivariate Polynomial Factorization, with A. Bostan, G. Lecerf, B. Salvy, B. Wiebelt.
  Proceedings ISSAC'04, pp. 42-49, ACM Press, 2004.
  PDF,PS.
• Fast Computation of Special Resultants, with A. Bostan, P. Flajolet, B. Salvy.
  Journal of Symbolic Computation 41(1): 1-29, 2006.
  PDF,PS.
• Polynomial evaluation and interpolation on special sets of points, with A. Bostan.
  Journal of Complexity 21(4): 420-446, 2005.
  PDF,PS.
• Construction of Secure Random Curves of Genus 2 over Prime Fields, with P. Gaudry.
  Proceedings Eurocrypt'04, pp. 239-256, Springer, 2004.
  PDF,PS.
• Properness Defects of Projections and Computation of One Point in Each Connected Component of a Real Algebraic Set, with M. Safey El Din.
  Discrete and Computational Geometry 32(3): 417-430, 2004.
  PS, PDF, DVI.
• Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves with A. Bostan, P. Gaudry.
  Proceedings Fq'7, pp. 40-58, Springer, 2003.
  PS, PDF, DVI.
  Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator with A. Bostan, P. Gaudry.
  SIAM Journal on Computing 36(6): 1777-1806, 2007.
  PS, PDF.
• Polar varieties and computation of one point in each connected component of a smooth real algebraic set, with M. Safey El Din.
  Proceedings ISSAC'03, pp. 224-231, ACM Press, 2003.
  PS, PDF, DVI.
• Tellegen's principle into practice, with A. Bostan, G. Lecerf.
  Proceedings ISSAC'03, pp. 37-44, ACM Press, 2003.
  PS, PDF, DVI.
• Degree bounds and lifting techniques for triangular sets.
  Proceedings ISSAC'02, pp. 238-245, ACM Press, 2002.
  PS, PDF, DVI.
  Complexity results for triangular sets, journal version.
  Journal of Symbolic Computation 36(3-4): 555-594, 2003.
  PS, PDF, DVI.
• Fast Algorithms for Zero-Dimensional Polynomial Systems Using Duality, with A. Bostan, B. Salvy.
  Applicable Algebra in Engineering, Communication and Computing 14(4): 239 - 272, 2003.
  PS, PDF, DVI.
• Uniform bounds for the number of rational points of families of curves of genus 2, with P. Gaudry, L. Kulesz, G. Matera.
  Proceedings WAIT'2001, pp 109-119, Anales JAIIO, 2001.
  PS, PDF, DVI.
  Uniform bounds for the number of rational points of families of curves of genus 2, long version, with L. Kulesz, G. Matera.
  Journal of Number Theory 108(2): 241-267.
  PS, PDF, DVI.
• Fast Multivariate Power Series Multiplication in Characteristic Zero, with G. Lecerf.
  SADIO Electronic Journal 5(1), 2003.
  PS, PDF, DVI.
• Solving the Birkhoff Interpolation Problem via the Critical Point Method: an experimental study, with F. Rouillier, M. Safey El Din.
  Proceedings ADG'2000 (LNAI 2061).
  PS, PDF, DVI.
• On the invariants of the quotients of the Jacobian of a curve of genus 2, with P. Gaudry.
  Proceedings AAECC 2001 (LNCS 2227), p 373-386.
  PS, PDF, DVI.
• Computing Parametric Geometric Resolutions.
  Applicable Algebra in Engineering, Communication and Computing 13(5): 349 - 393, 2003.
  PS, PDF, DVI.
• Solving some overdetermined polynomial systems, with M. Giusti.
  Proceedings ISSAC'99, pp. 1-8, ACM Press, 1999.
  PS, PDF, DVI.
• Ph. D. Thesis.
  PS.
• Some known results on polynomial factorization over towers of field extensions, with G. Renault.
  PDF.