Computable objects and algorithms

The development of basic computable objects is somehow on demand and depends on all the other research directions. However, some critical computations are already known to be bottlenecks and are sources of constant efforts.

Computations with algebraic numbers appear in almost all our activities: when working with number fields in our work in algorithmic number theory as well as in all the computations that involve the use of solutions of zero-dimensional systems of polynomial equations. Among the identified problems: finding good representations for single number fields (optimizing the size and degree of the defining polynomials), finding good representations for towers or products of number fields (typically working with a tower or finding a unique good extension), efficiently computing in practice with number fields (using certified approximation vs working with the formal description based on polynomial arithmetics). Strong efforts are currently done in the understanding of the various strategies by means of tight theoretical complexity studies and many other efforts will be required to find the right representation for the right problem in practice. For example, for isolating critical points of plane algebraic curves, it is still unclear (at least the theoretical complexity cannot help) that an intermediate formal parameterization is more efficient than a triangular decomposition of the system and it is still unclear that these intermediate computations could be dominated in time by the certified final approximation of the roots.

  • [PDF] [DOI] C. Katsamaki and F. Rouillier, “On Isolating Roots in a Multiple Field Extension,” in ISSAC ’23: 2023 International Symposium on Symbolic and Algebraic Computation, Tromso, Norway, 2023, pp. 363-371.
    [Bibtex] 
    @inproceedings{katsamaki:hal-04116621,
TITLE = {{On Isolating Roots in a Multiple Field Extension}},
AUTHOR = {Katsamaki, Christina and Rouillier, Fabrice},
URL = {https://hal.science/hal-04116621},
BOOKTITLE = {{ISSAC '23: 2023 International Symposium on Symbolic and Algebraic Computation}},
ADDRESS = {Tromso, Norway},
PUBLISHER = {{ACM}},
PAGES = {363-371},
YEAR = {2023},
MONTH = Jul,
DOI = {10.1145/3597066.3597107},
KEYWORDS = {Root isolation ; Field extension ; Bit-complexity},
PDF = {https://hal.science/hal-04116621/file/Isolating_roots_in_a_multiple_field_extension__HAL_.pdf},
HAL_ID = {hal-04116621},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] J. Tonelli-Cueto, “A Geometric Summation of the Geometric Series,” The American Mathematical Monthly, pp. 1-1, 2022.
    [Bibtex] 
    @article{tonellicueto:hal-03779492,
TITLE = {{A Geometric Summation of the Geometric Series}},
AUTHOR = {Tonelli-Cueto, Josu{\'e}},
URL = {https://inria.hal.science/hal-03779492},
JOURNAL = {{The American Mathematical Monthly}},
PUBLISHER = {{Mathematical Association of America}},
PAGES = {1-1},
YEAR = {2022},
MONTH = Sep,
DOI = {10.1080/00029890.2022.2115825},
PDF = {https://inria.hal.science/hal-03779492/file/A_Geometric_Summation_of_the_Geometric_Series_AM.pdf},
HAL_ID = {hal-03779492},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] F. Cucker, A. A. Ergür, and J. Tonelli-Cueto, “On the Complexity of the Plantinga-Vegter Algorithm,” Discrete and Computational Geometry, 2022.
    [Bibtex] 
    @article{cucker:hal-02552018,
TITLE = {{On the Complexity of the Plantinga-Vegter Algorithm}},
AUTHOR = {Cucker, Felipe and Erg{\"u}r, Alperen A. and Tonelli-Cueto, Josu{\'e}},
URL = {https://inria.hal.science/hal-02552018},
JOURNAL = {{Discrete and Computational Geometry}},
PUBLISHER = {{Springer Verlag}},
YEAR = {2022},
MONTH = Aug,
DOI = {10.1007/s00454-022-00403-x},
KEYWORDS = {Complexity ; Subdivision methods ; Plantinga-Vegter algorithm},
PDF = {https://inria.hal.science/hal-02552018/file/On_the_Complexity_of_the_Plantinga_Vegter_algorithm%20%282%29.pdf},
HAL_ID = {hal-02552018},
HAL_VERSION = {v1},
}

  • [DOI] M. Levent Do{u g}an, A. Ergür, J. Mundo, and E. Tsigaridas, “The Multivariate Schwartz–Zippel Lemma,” SIAM Journal on Discrete Mathematics, vol. 36, iss. 2, pp. 888-910, 2022.
    [Bibtex] 
    @article{leventdoan:hal-03637826,
TITLE = {{The Multivariate Schwartz--Zippel Lemma}},
AUTHOR = {Levent Do{\u g}an, Mahmut and Erg{\"u}r, Alperen and Mundo, Jake and Tsigaridas, Elias},
URL = {https://inria.hal.science/hal-03637826},
JOURNAL = {{SIAM Journal on Discrete Mathematics}},
PUBLISHER = {{Society for Industrial and Applied Mathematics}},
VOLUME = {36},
NUMBER = {2},
PAGES = {888-910},
YEAR = {2022},
MONTH = Jun,
DOI = {10.1137/20M1333869},
KEYWORDS = {Schwartz-Zippel lemma ; Combinatorial Nullstellesantz ; Combinatorial geometry ; Polynomial partitioning ; Incidence geometry ; Resultant ; Generalized characteristic polynomial},
HAL_ID = {hal-03637826},
HAL_VERSION = {v1},
}

  • [PDF] [DOI] M. Radons and J. Tonelli-Cueto, “Generalized Perron roots and solvability of the absolute value equation,” in Discrete Mathematics Days 2022, Santander, Spain, 2022, pp. 237-242.
    [Bibtex] 
    @inproceedings{radons:hal-03739462,
TITLE = {{Generalized Perron roots and solvability of the absolute value equation}},
AUTHOR = {Radons, Manuel and Tonelli-Cueto, Josu{\'e}},
URL = {https://inria.hal.science/hal-03739462},
NOTE = {This is a conference version. The other entry, with the same name, is for the journal version.},
BOOKTITLE = {{Discrete Mathematics Days 2022}},
ADDRESS = {Santander, Spain},
EDITOR = {L.F. Tabera Alonso},
PUBLISHER = {{Editorial Universidad de Cantabria}},
PAGES = {237-242},
YEAR = {2022},
MONTH = Jul,
DOI = {10.22429/Euc2022.016},
PDF = {https://inria.hal.science/hal-03739462/file/DMD2020_paper_51_submission.pdf},
HAL_ID = {hal-03739462},
HAL_VERSION = {v1},
}

  • [PDF] A. Chalkis, V. Fisikopoulos, E. Tsigaridas, and H. Zafeiropoulos, “Geometric algorithms for sampling the flux space of metabolic networks,” in The 37th International Symposium on Computational Geometry (SoCG), Buffalo, United States, 2021.
    [Bibtex] 
    @inproceedings{chalkis:hal-03047049,
TITLE = {{Geometric algorithms for sampling the flux space of metabolic networks}},
AUTHOR = {Chalkis, Apostolos and Fisikopoulos, Vissarion and Tsigaridas, Elias and Zafeiropoulos, Haris},
URL = {https://inria.hal.science/hal-03047049},
BOOKTITLE = {{The 37th International Symposium on Computational Geometry (SoCG)}},
ADDRESS = {Buffalo, United States},
YEAR = {2021},
MONTH = Jun,
KEYWORDS = {Flux analysis ; Metabolic networks ; Convex polytopes ; Random walks ; Sampling ; 2012 ACM Subject Classification Mathematics of computing$\rightarrow$Mathematical software ; Applied computing$\rightarrow$ Systems biology ; Computing methodologies$\rightarrow$Modeling and simulation phrases Flux analysis ; metabolic networks ; convex polytopes ; random walks ; sampling},
PDF = {https://inria.hal.science/hal-03047049v2/file/metabolic_networks.pdf},
HAL_ID = {hal-03047049},
HAL_VERSION = {v2},
}
  • [PDF] [DOI] I. Z. Emiris, A. Mantzaflaris, and E. Tsigaridas, “Multilinear Polynomial Systems: Root Isolation and Bit Complexity,” Journal of Symbolic Computation, vol. 105, pp. 145-164, 2021.
    [Bibtex] 
    @article{emiris:hal-02099556,
TITLE = {{Multilinear Polynomial Systems: Root Isolation and Bit Complexity}},
AUTHOR = {Emiris, Ioannis Z. and Mantzaflaris, Angelos and Tsigaridas, Elias},
URL = {https://inria.hal.science/hal-02099556},
NOTE = {Special Issue of the Journal of Symbolic Computation on Milestones in Computer Algebra (MICA 2016)},
JOURNAL = {{Journal of Symbolic Computation}},
PUBLISHER = {{Elsevier}},
SERIES = {Special Issue on Milestones in Computer Algebra (MICA 2016)},
VOLUME = {105},
PAGES = {145-164},
YEAR = {2021},
DOI = {10.1016/j.jsc.2020.06.005},
KEYWORDS = {Bit complexity ; Primitive element ; Cayley-Koszul complex ; Resultant matrix ; Rational univariate representation ; DMM separation bound},
PDF = {https://inria.hal.science/hal-02099556/file/emt-bhomo-jsc.pdf},
HAL_ID = {hal-02099556},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] E. Bartzos, I. Emiris, J. Legerský, and E. Tsigaridas, “On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs,” in ISSAC ’18 International Symposium on Symbolic and Algebraic Computation, New York, United States, 2018, pp. 55-62.
    [Bibtex] 
    @inproceedings{bartzos:hal-01710518,
TITLE = {{On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs}},
AUTHOR = {Bartzos, Evangelos and Emiris, Ioannis and Legersk{\'y}, Jan and Tsigaridas, Elias},
URL = {https://hal.science/hal-01710518},
BOOKTITLE = {{ISSAC '18 International Symposium on Symbolic and Algebraic Computation}},
ADDRESS = {New York, United States},
EDITOR = {Carlos Arreche},
PUBLISHER = {{ACM}},
PAGES = {55-62},
YEAR = {2018},
MONTH = Jul,
DOI = {10.1145/3208976.3208994},
KEYWORDS = {spatial embedding ; mixed volume ; rigid graph ; Cayley-Menger matrix ; coupler curve ; real bound},
PDF = {https://hal.science/hal-01710518v2/file/On%20the%20maximal%20number%20of%20real%20embeddings%20of%20spatial%20minimally%20rigid%20graphs.pdf},
HAL_ID = {hal-01710518},
HAL_VERSION = {v2},
}

  • [PDF] [DOI] L. Busé, A. Mantzaflaris, and E. Tsigaridas, “Matrix formulae for Resultants and Discriminants of Bivariate Tensor-product Polynomials,” Journal of Symbolic Computation, vol. 98, pp. 65-83, 2020.
    [Bibtex] 
    @article{buse:hal-01654263,
TITLE = {{Matrix formulae for Resultants and Discriminants of Bivariate Tensor-product Polynomials}},
AUTHOR = {Bus{\'e}, Laurent and Mantzaflaris, Angelos and Tsigaridas, Elias},
URL = {https://inria.hal.science/hal-01654263},
JOURNAL = {{Journal of Symbolic Computation}},
PUBLISHER = {{Elsevier}},
VOLUME = {98},
PAGES = {65-83},
YEAR = {2020},
MONTH = Jun,
DOI = {10.1016/j.jsc.2019.07.007},
KEYWORDS = {Singular locus ; Koszul resultant matrix ; Tensor-product ; Eliminant ; Mixed discriminant ; Resultant ; Mixed polynomial system},
PDF = {https://inria.hal.science/hal-01654263/file/bmt-j-bivar.pdf},
HAL_ID = {hal-01654263},
HAL_VERSION = {v1},
}
  • [PDF] [DOI] I. Z. Emiris, B. Mourrain, and E. Tsigaridas, “Separation bounds for polynomial systems,” Journal of Symbolic Computation, vol. 101, pp. 128-151, 2020.
    [Bibtex] 
    @article{emiris:hal-01105276,
TITLE = {{Separation bounds for polynomial systems}},
AUTHOR = {Emiris, Ioannis Z. and Mourrain, Bernard and Tsigaridas, Elias},
URL = {https://inria.hal.science/hal-01105276},
JOURNAL = {{Journal of Symbolic Computation}},
PUBLISHER = {{Elsevier}},
VOLUME = {101},
PAGES = {128-151},
YEAR = {2020},
DOI = {10.1016/j.jsc.2019.07.001},
KEYWORDS = {Polynomial system ; Positive polynomial ; Subdivision algorithm ; Height of the resultant ; Arithmetic Nullstellens{\"a}tze ; Separation bound ; Sparse resultant ; DMM ; Separation bounds},
PDF = {https://inria.hal.science/hal-01105276v5/file/emt-dmm-j.pdf},
HAL_ID = {hal-01105276},
HAL_VERSION = {v5},
}

 



Comments are closed.