Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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. 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. We demonstrate its capabilities by providing a new probabilistic complexity analysis for the Plantinga-Vegter algorithm, which covers both random sparse (alas a restricted sparseness structure) polynomials and random Gaussian polynomials. We present explicit results with structured random polynomials for problems with two or more dimensions. Additionally, we provide some estimates of the separation bound of a univariate polynomial in our current framework.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Josué Tonelli-Cueto <>
Submitted on : Monday, June 8, 2020 - 10:54:47 AM
Last modification on : Thursday, April 15, 2021 - 3:08:15 PM



Josué Tonelli-Cueto, Elias Tsigaridas. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces. Proceedings of the 2020 International Symposium on Symbolic and Algebraic Computation, ISSAC'20, Jul 2020, Kalamata, Greece. pp.434-441, ⟨10.1145/3373207.3404054⟩. ⟨hal-02736942v2⟩



Record views


Files downloads