Pith. sign in

REVIEW 3 major objections 4 minor 67 references

Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that on random integer-coefficient polynomials, the Descartes solver isolates all real roots in quasi-linear expected bit complexity, giving a theoretical explanation for why this simple algorithm outperforms…

desk verdict Valuable framework, but two load-bearing proof steps are broken: the small-ball argument for the Descartes bound applies to coefficients the model doesn't constrain, and the Sturm analysis multiplies dependent expectations. read the letter →

arxiv 2506.04436 v1 pith:GMJDE2GO submitted 2025-06-04 cs.SC cs.CCmath.AGmath.PR

Alperen A. Ergür , Josué Tonelli-Cueto , Elias Tsigaridas This is my paper
classification cs.SCcs.CCmath.AGmath.PR MSC 68Q2568W2065H0412Y05
keywords realrootisolationDescartessolversmoothedanalysisaverage-casecomplexityrandombitpolynomialsconditionnumbersseparationbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Symbolic computation usually measures algorithms by worst-case bit complexity, yet the algorithms that win in practice are often those with poor worst-case bounds. This paper attacks that gap for real root isolation, the task of returning one interval per real root of an integer polynomial. It introduces a probabilistic model of integer polynomials, called random bit polynomials, and proves that the Descartes solver, the simple subdivision method based on Descartes' rule of signs, has expected bit complexity that is quasi-linear in the degree and coefficient bitsize when the coefficients are random and the bitsize is not too small. The same machinery yields expected and smoothed bounds for the Sturm solver, for the hybrid Newton-based solver ANewDsc, and for a sparse solver. The upshot is a first theoretical explanation of why Descartes routinely beats algorithms with better worst-case guarantees.

What carries the argument

The argument rests on two instance-specific quantities and a probabilistic model. The model is a random bit polynomial, where coefficients are independent integer random variables and the only distributional constraint is on the leading and trailing coefficients, measured by uniformity $u(\mathfrak{f})$. The first quantity is the real global condition number $\mathrm{C_R}(f)$, the largest local condition number $C(f,z)=\|f\|_1/\max(|f(z)|,|f'(z)|/d)$ on the interval; through the separation bound, it controls the depth of the Descartes subdivision tree. The second is the number $\varrho(f)$ of complex roots lying in the union of hyperbolic discs, the Obreshkoff areas, covering the interval; through an Obreshkoff theorem, this controls the width of the subdivision tree. Small-ball probability estimates for discrete random vectors give tail bounds on both quantities, and the expected complexity follows by combining expected width and depth.

What would settle it

Run the Descartes solver on uniform random bit polynomials with $\tau = \lceil\log_2 d\rceil$ for increasing $d$ and count subdivision steps; the theorem predicts an expected number of steps of $\tilde{O}(1)$ and expected bit complexity $\tilde{O}_B(d\log d + d^2)$, so growth like a positive power of $d$ would falsify the central claim.

Watch

Extended reading notes

Core claim

The central result, Theorem 1.11 (restated as Theorem 3.8), is that if $\mathfrak{f}$ is a random bit polynomial of degree $d$, bitsize $\tau(\mathfrak{f}) \geq \Omega(\log d + u(\mathfrak{f}))$, and uniformity $u(\mathfrak{f})$, then the Descartes solver isolates the real roots in $I = [-1,1]$ in expected bit complexity $\tilde{O}_B\big(d\tau(\mathfrak{f})(1+u(\mathfrak{f}))^3 + d^2(1+u(\mathfrak{f}))^4\big)$; for uniform random bit polynomials this reduces to $\tilde{O}_B(d\tau + d^2)$. Since the best worst-case bound for root finding is $\tilde{O}_B(d^2\tau)$, the expected bound is better by roughly a factor of $d$ when $d$ and $\tau$ are comparable. The same condition-based analysis gives expected bounds for the Sturm solver, $\tilde{O}_B(d^2\tau(\mathfrak{f})(1+u(\mathfrak{f}))^3)$, for ANewDsc, $\tilde{O}_B((d^2+d\tau(\mathfrak{f}))(1+u(\mathfrak{f}))^2)$, and for the sparse JS solver, $\tilde{O}_B(|M|^{12}\tau^2\log^3 d)$ on sparse random bit polynomials.

Load-bearing premise

The bounds require the coefficients to be independent random integers with enough entropy, in particular $\tau(\mathfrak{f}) = \Omega(\log d + u(\mathfrak{f}))$, so the leading and trailing coefficients are not too concentrated; if real inputs are correlated or adversarial, the expected and smoothed bounds do not apply.

Editorial extensions

If this is right

  • For uniform random bit polynomials with $d\approx\tau$, Descartes' expected bit complexity $\tilde{O}_B(d\tau+d^2)$ beats Pan's record worst-case bound $\tilde{O}_B(d^2\tau)$ by a factor of $d$.
  • The Sturm solver, as commonly implemented, has an expected lower bound $\Omega(d^3+d^2\tau)$ (Proposition 3.13), which is worse than Descartes' expected bound by an order of magnitude; the paper reads this as the first theoretical explanation of Descartes' practical superiority over Sturm.
  • The hybrid symbolic-numeric solver ANewDsc inherits essentially the same expected complexity as Descartes, $\tilde{O}_B((d^2+d\tau)(1+u)^2)$, so the Newton acceleration is not needed to explain the practical speed.
  • The sparse solver of Jindal and Sagraloff has expected bit complexity $\tilde{O}_B(|M|^{12}\tau^2\log^3 d)$ for sparse random bit polynomials, giving the first non-worst-case analysis of a sparse root isolation solver.
  • The random model is flexible enough to cover random supports, random signs, exact-bitsize coefficients, and smoothed perturbations of a fixed polynomial, so the results extend beyond the uniform model to structured randomness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implicit consequence of the proof is that the entropy of the leading and trailing coefficients, rather than of all coefficients, drives the speed of Descartes; a cheap test would be to randomize only $c_0$ and $c_d$ in a worst-case polynomial family and measure the subdivision-tree size.
  • The decomposition into depth (condition number) and width (complex roots near the real axis, via Obreshkoff areas) is not specific to Descartes and could yield smoothed bounds for other subdivision schemes, such as complex root isolation by the Pellet test or continued-fraction solvers.
  • For inputs that arise from elimination or cylindrical algebraic decomposition, coefficients are correlated, so the random model may not apply; benchmarking the same random model against those structured inputs would show where the explanation stops.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a beyond-worst-case framework for real root isolation of integer polynomials, based on a discrete random coefficient model (Definition 1.2) in which only the leading and trailing coefficients need to have small atom probabilities; uniformity u(f) measures how far these endpoints are from uniform random bit coefficients. The main results are expected bit-complexity bounds for the Descartes solver (Theorem 3.8), the Sturm solver (Theorem 3.11), ANewDsc (Theorem 3.15), and the JS-sparse solver (Theorem 3.17). The proofs combine condition-number bounds for the separation bound, the Obreshkoff-lens/area technique to control the subdivision width via the number of roots near the real axis, and small-ball probability estimates for discrete random coefficients.

Significance. If the main bounds hold, this is a substantial contribution: it gives expected and smoothed bit-complexity results for classical symbolic root isolation in a discrete coefficient model, and it offers a concrete mechanism by which Descartes can outperform algorithms with superior worst-case bounds. The paper is commendably explicit in its constants, the random model is flexible and precisely defined, and there is no sign of parameter fitting or circular reliance on the target theorems. The main caveat is that the 'explains practice' conclusion is conditional on the random model; the paper provides no evidence that real application inputs resemble independent random coefficient vectors with sufficient endpoint entropy. That is a framing limitation rather than a technical error. The current proof gaps in Theorem 2.10 and Theorem 3.11 are serious but appear repairable, so the paper merits a major revision rather than rejection.

major comments (3)
  1. [§2.4.2 (Theorem 2.10)] The proof of Theorem 2.10 applies Proposition 2.7 to the full coefficient vector with A = [1, x, ..., x^{d-1}, x^d], but Proposition 2.7 requires a uniform bound w on the atom probabilities of every coordinate of the random vector. Definition 1.2 only guarantees this for the endpoint coefficients c0 and cd, and indeed Example 1.7 allows A = {0, d}, in which case the middle coefficients are deterministic and have atom probability 1. Consequently the displayed bound P(e||f||_1/|f(x)| >= s) <= 44 d^2 e^{u(f)}/s is not established under the paper's own model, and the gap propagates to Corollary 2.11 and hence to the expected-complexity bounds in Theorems 3.8, 3.15, and 3.17. The gap appears repairable by conditioning on the middle coefficients and applying Proposition 2.7 to the two endpoint coefficients with A = [1, x^d] and with the middle contribution absorbed into b; the authors should supply this argument and verify the constants.
  2. [§3.2 (Theorem 3.11)] The proof of Theorem 3.11 explicitly states: 'Notice that we implicitly assume that the random variables ρ(f) and CR(f) are independent.' This assumption is generally false: a root of f in the hyperbolic disks Ω_d near the real axis forces |f| to be small at nearby real points, which by the definition of CR(f) makes CR(f) large, so the two quantities are positively correlated. The proof needs a replacement such as a Cauchy-Schwarz or Hölder argument using Corollary 2.11 with ℓ = 2 and Corollary 2.6 with ℓ = 4 to bound E[ρ min{(log CR)^2, d^2 τ}] without independence. As written, the expected Sturm bound eO_B(d^2 τ (1+u)^3) is not derived.
  3. [§3.4 (Theorem 3.17)] The proof of Theorem 3.17 is only the sentence 'the following result is immediate'; the missing calculation is the expectation of max{log^2||f||_1, log^3 CR(f)} under the stated hypotheses. In particular, one must invoke Corollary 2.6 with ℓ = 3 and account for the assumption τ > log^3 d. The derivation is short, but it should be written out because Theorem 3.17 is one of the four central claims and no calculation is currently shown.
minor comments (4)
  1. [Throughout] Please unify the capitalization and spelling of algorithm names: 'descartes' vs 'Descartes', 'sturm' vs 'Sturm', and 'Obreshkoff' vs 'Obreskoff' are used inconsistently.
  2. [Abstract and Introduction] The claim that the results 'explain the surprising efficiency' of the Descartes solver should be softened to 'are consistent with' or 'offer a possible explanation', since the paper provides no empirical evidence that practical input distributions match the random bit polynomial model.
  3. [§2.4.2 (Theorem 2.10 proof)] In the sentence 'for any s <= 2^{τ(f)}', the subsequent substitution s = e^{t/N} with t <= τ(f) N gives s <= e^{τ(f)}, which is compatible with s <= 2^{τ(f)} only if the wording is made precise; please clarify the constraint.
  4. [Throughout] There are several typos, including 'supress' (p. 8), 'the fist algorithm' (p. 24), and the missing parentheses in the display of Theorem 1.1 for the JS-sparse bound; a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: complexity theorems are derived from the randomness model and independent condition-number results; the Theorem 2.10 gap is a correctness issue, not a circular reduction.

full rationale

I find no circularity in the derivation chain. The main expected/smoothed complexity bounds (Theorems 3.8, 3.11, 3.15, 3.17) are proved from instance-based deterministic bounds (Theorem 3.7, Lemma 3.9) plus probabilistic estimates (Theorems 2.5 and 2.10 and Corollaries 2.6 and 2.11) whose proofs use the randomness model of Definition 1.2 and the small-ball estimate Proposition 2.7; CR(f) and rho(f) are defined from the input polynomial itself, not from the algorithm's runtime, so the final expectation is not an identity with the model. The condition-number separation results (Theorems 2.2 and 2.4) are cited from the authors' prior work [61], but these are parameter-free theorems with explicit assumptions that do not include the target expected-complexity result, so by the rubric this self-citation is independent support rather than circularity. I do flag a non-circular correctness gap: in the proof of Theorem 2.10 (Section 2.4.2), Proposition 2.7 is applied to the full coefficient vector A=[1,x,...,x^{d-1},x^d], whereas Definition 1.2 only bounds atom probabilities of c0 and cd, leaving middle coefficients potentially deterministic (e.g., Example 1.7); consequently the claimed bound P(e||f||_1/|f(x)| >= s) <= 44 d^2 e^{u(f)}/s is not justified as written, and this gap propagates to Corollary 2.11 and Theorem 3.8. This is a proof gap, not a circular reduction, and does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper fits no free parameters: all constants in the probability bounds are explicit, and the model parameters (d, τ, u) are input parameters. The main load-bearing assumptions are the random coefficient model, the imported condition-number bounds, and (in the Sturm proof) an unjustified independence claim.

assumptions (6)
  • domain assumption Random bit polynomial model: independent coefficients with bounded atom probabilities, and condition τ(𝔣)=Ω(log d+u(𝔣))
    Definition 1.2 and Theorems 1.11-1.16. The entire average/smoothed analysis is conditional on this data model and the entropy condition.
  • standard math Condition-number estimates from [61]: ΔR_ε(f) ≥ 1/(12d CR(f)) and Lipschitz property of the condition number
    Used in Theorem 2.4 and Corollary 2.6 to bound the depth of subdivision trees. Cited from the authors' prior work; treated as a black box.
  • standard math Obreshkoff lens/area theorem and subadditivity of sign variations
    Theorems 3.4 and 3.5, used to bound the number of sign variations by the number of complex roots near the interval. Cited from [40, 35].
  • standard math One and two circle theorem
    Theorem 3.6, used to guarantee termination when intervals are small relative to the ε-real separation. Cited from [1, 35].
  • ad hoc to paper Independence of ρ(𝔣) and CR(𝔣) in the Sturm expected complexity proof
    Invoked in the proof of Theorem 3.11 to factor E[ρ log CR]. The variables are both functions of the same random polynomial and are not generally independent; this premise is not justified.
  • domain assumption Assumption 3.12: current Sturm implementations use the standard (not half-gcd) representation of Sturm sequences
    Used in Proposition 3.13 to explain the practical inferiority of Sturm. This is a claim about implementations, not a mathematical fact.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms." pith.science (2026). https://pith.science/paper/GMJDE2GO

@misc{pith2026250604436,
  author       = {Pith},
  title        = {Pith review of: Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GMJDE2GO}},
  note         = {Machine review of arXiv:2506.04436}
}
read the original abstract

We introduce beyond-worst-case analysis into symbolic computation. This is an extensive field which almost entirely relies on worst-case bit complexity, and we start from a basic problem in the field: isolating the real roots of univariate polynomials. This is a fundamental problem in symbolic computation and it is arguably one of the most basic problems in computational mathematics. The problem has a long history decorated with numerous ingenious algorithms and furnishes an active area of research. However, most available results in literature either focus on worst-case analysis in the bit complexity model or simply provide experimental benchmarking without any theoretical justifications of the observed results. We aim to address the discrepancy between practical performance of root isolation algorithms and prescriptions of worst-case complexity theory: We develop a smoothed analysis framework for polynomials with integer coefficients to bridge this gap. We demonstrate (quasi-)linear (expected and smoothed) complexity bounds for Descartes algorithm, that is one most well know symbolic algorithms for isolating the real roots of univariate polynomials with integer coefficients. Our results explain the surprising efficiency of Descartes solver in comparison to sophisticated algorithms that have superior worst-case complexity. We also analyse the Sturm solver, ANewDsc a symbolic-numeric algorithm that combines Descartes with Newton operator, and a symbolic algorithm for sparse polynomials.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

67 extracted references · 56 canonical work pages

  1. [1]

    Alberto Alesina and Massimo Galuzzi. 1998. A new proof of Vincent’s theorem. Enseign. Math. (2) 44, 3-4 (1998), 219–256

    work page 1998

  2. [2]

    Arora and B

    S. Arora and B. Barak. 2009. Computational complexity: a modern approach . Cambridge University Press, Cambridge. xxiv+579 pages. https://doi.org/10.1017/CBO9780511804090

    doi:10.1017/cbo9780511804090 2009

  3. [3]

    Ruben Becker, Michael Sagraloff, Vikram Sharma, and Chee Yap. 2018. A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration. J. Symbolic Comput. 86 (2018), 51–96. https://doi.org/10.1016/j.jsc.2017.03.009

    doi:10.1016/j.jsc.2017.03.009 2018

  4. [4]

    Dario Andrea Bini and Giuseppe Fiorentino. 2000. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms 23, 2-3 (2000), 127–173. https://doi.org/10.1023/A:1019199917103

    doi:10.1023/a:1019199917103 2000

  5. [5]

    L. Blum, F. Cucker, M. Shub, and S. Smale. 1998. Complexity and real computation . Springer-Verlag, New York. xvi+453 pages. https://doi.org/10.1007/978-1-4612-0701-6

    doi:10.1007/978-1-4612-0701-6 1998

  6. [6]

    Marco Bodrato and Alberto Zanoni. 2011. Long integers and polynomial evaluation with Estrin’s scheme. In 2011 13th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing . IEEE, 39–46. Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms • 25

    work page 2011

  7. [7]

    Peter Bürgisser and Felipe Cucker. 2013. Condition: The geometry of numerical algorithms . Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Vol. 349. Springer, Heidelberg. xxxii+554 pages. https: //doi.org/10.1007/978-3-642-38896-5

    work page doi:10.1007/978-3-642-38896-5 2013

  8. [8]

    Burr and Felix Krahmer

    Michael A. Burr and Felix Krahmer. 2012. SqFreeEVAL: an (almost) optimal real-root isolation algorithm. J. Symbolic Comput. 47, 2 (2012), 153–166. https://doi.org/10.1016/j.jsc.2011.08.022

    work page doi:10.1016/j.jsc.2011.08.022 2012

Show all 67 references
  1. [9]

    Castro, J

    D. Castro, J. L. Montaña, L. M. Pardo, and J. San Martín. 2002. The distribution of condition numbers of rational data of bounded bit length. Found. Comput. Math. 2, 1 (2002), 1–52. https://doi.org/10.1007/s002080010017

    2002 doi

  2. [10]

    J. H. Davenport. 1988. Cylindrical algebraic decomposition. Technical Report 88–10. University of Bath. http://www.bath.ac.uk/masjhd/

    1988

  3. [11]

    Jean-Pierre Dedieu. 2006. Points fixes, zéros et la méthode de Newton. Mathématiques & Applications (Berlin) [Mathematics & Applications], Vol. 54. Springer, Berlin. xii+196 pages

    2006

  4. [12]

    Ilias Diakonikolas and Daniel M Kane. 2023. Algorithmic high-dimensional robust statistics . Cambridge university press

    2023

  5. [13]

    R. G. Downey and M. R. Fellows. 2013. Fundamentals of parameterized complexity . Springer, London. xxx+763 pages. https://doi.org/10. 1007/978-1-4471-5559-1

    2013

  6. [14]

    Zilin Du, Vikram Sharma, and Chee K. Yap. 2007. Amortized bound for root isolation via Sturm sequences. In Symbolic-numeric computation (Trends Math.). Birkhäuser, Basel, 113–129. https://doi.org/10.1007/978-3-7643-7984-1_8

    2007 doi

  7. [15]

    Arno Eigenwillig, Lutz Kettner, Werner Krandick, Kurt Mehlhorn, Susanne Schmitt, and Nicola Wolpert. 2005. A Descartes algorithm for polynomials with bit-stream coefficients. In Computer algebra in scientific computing (Lecture Notes in Comput. Sci., Vol. 3718) . Springer, Ber...

    2005 doi

  8. [17]

    Ioannis Emiris, Bernard Mourrain, and Elias Tsigaridas. 2020. Separation bounds for polynomial systems. J. Symbolic Comput. 101 (2020), 128–151. https://doi.org/10.1016/j.jsc.2019.07.001

    2020 doi

  9. [18]

    Emiris, André Galligo, and Elias P

    Ioannis Z. Emiris, André Galligo, and Elias P. Tsigaridas. 2010. Random polynomials and expected complexity of bisection methods for real solving. In ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation . ACM, New York, 235–242. http...

    2010

  10. [19]

    I. Z. Emiris, B. Mourrain, and E. P. Tsigaridas. 2008. Real Algebraic Numbers: Complexity Analysis and Experimentation. In Reliable Implementations of Real Number Algorithms: Theory and Practice (LNCS, Vol. 5045) , P. Hertling, C. Hoffmann, W. Luther, and N. Revol (Eds.). Spri...

    2008

  11. [20]

    Emiris, Victor Y

    Ioannis Z. Emiris, Victor Y. Pan, and Elias P. Tsigaridas. 2012. Algebraic algorithms. In Computing Handbook Set - Computer Science (3nd ed.), Teofilo Gonzalez (Ed.). Vol. I. CRC Press Inc., Boca Raton, Florida, Chapter 10, 10–1–10–30

    2012

  12. [21]

    Alperen Ergür, Grigoris Paouris, and J Rojas. 2021. Smoothed analysis for the condition number of structured real polynomial systems. Math. Comp. 90, 331 (2021), 2161–2184

    2021

  13. [22]

    Alperen Ergür, Josué Tonelli-Cueto, and Elias Tsigaridas. 2022. Beyond worst-case analysis for root isolation algorithms. In Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC) . 139–148

    2022

  14. [23]

    Paula Escorcielo and Daniel Perrucci. 2017. On the Davenport-Mahler bound. J. Complexity 41 (2017), 72–81. https://doi.org/10.1016/j. jco.2016.12.001

    2017 doi

  15. [24]

    Steven Fortune. 2002. An iterated eigenvalue algorithm for approximating roots of univariate polynomials. J. Symbolic Comput. 33, 5 (2002), 627–646. https://doi.org/10.1006/jsco.2002.0526 Computer algebra (London, ON, 2001)

    2002

  16. [25]

    Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. 2020. Smoothed analysis of online and differentially private learning.Advances in Neural Information Processing Systems 33 (2020), 9203–9215

    2020

  17. [26]

    William Hart and Andrew Novocin. 2011. Practical divide-and-conquer algorithms for polynomial arithmetic. In International Workshop on Computer Algebra in Scientific Computing . Springer, 200–214

    2011

  18. [27]

    Tsigaridas, Zafeirakis Zafeirakopoulos, Ioannis Z

    Michael Hemmer, Elias P. Tsigaridas, Zafeirakis Zafeirakopoulos, Ioannis Z. Emiris, Menelaos I. Karavelas, and Bernard Mourrain. 2009. Experimental Evaluation and Cross-Benchmarking of Univariate Real Solvers. In Proceedings of the 2009 Conference on Symbolic Numeric Computati...

    2009

  19. [28]

    Nicholas J. Higham. 2002. Accuracy and stability of numerical algorithms (second ed.). Society for Industrial and Applied Mathematics (SIAM, Philadelphia, PA. xxx+680 pages. https://doi.org/10.1137/1.9780898718027

    2002 doi

  20. [29]

    Rémi Imbach and Guillaume Moroz. 2023. Fast evaluation and root finding for polynomials with floating-point coefficients. InProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (ISSAC 2023) . ACM. https://doi.org/10.1145/3597066.3597112

    2023

  21. [30]

    Rémi Imbach and Victor Y Pan. 2020. New progress in univariate polynomial root finding. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation . 249–256

    2020

  22. [31]

    Gorav Jindal and Michael Sagraloff. 2017. Efficiently computing real roots of sparse polynomials. InProc ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC) . 229–236. 26 • A.A. Ergür, J. Tonelli-Cueto and E. Tsigaridas

    2017

  23. [32]

    Johnson, Werner Krandick, Kevin Lynch, David G

    Jeremy R. Johnson, Werner Krandick, Kevin Lynch, David G. Richardson, and Anatole D. Ruslanov. 2006. High-performance implemen- tations of the Descartes method. In ISSAC 2006. ACM, New York, 154–161. https://doi.org/10.1145/1145768.1145797

    2006

  24. [33]

    Peter Kirrinnis. 1998. Partial fraction decompostion in C(z) and simultaneous Newton iteration for factorization in C[z]. J. Complexity 14, 3 (1998), 378–444. https://doi.org/10.1006/jcom.1998.0481

    1998

  25. [34]

    Alexander Kobel, Fabrice Rouillier, and Michael Sagraloff. 2016. Computing real roots of real polynomials ... and now for real!. In Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation . ACM, New York, 303–310. https: //doi.org/10.1145/2930...

    2016

  26. [35]

    Werner Krandick and Kurt Mehlhorn. 2006. New bounds for the Descartes method. J. Symbolic Comput. 41, 1 (2006), 49–66. https: //doi.org/10.1016/j.jsc.2005.02.004

    2006 doi

  27. [36]

    Livshyts, G

    G. Livshyts, G. Paouris, and P. Pivovarov. 2016. On sharp bounds for marginal densities of product measures.Israel Journal of Mathematics 216, 2 (2016), 877–889. https://doi.org/10.1007/s11856-016-1431-5

    2016 doi

  28. [37]

    McNamee and Victor Y

    John M. McNamee and Victor Y. Pan. 2013. Numerical methods for roots of polynomials. Part II . Studies in Computational Mathematics, Vol. 16. Elsevier/Academic Press, Amsterdam. xxii+726 pages

    2013

  29. [38]

    Kurt Mehlhorn, Michael Sagraloff, and Pengming Wang. 2015. From approximate factorization to root isolation with application to cylindrical algebraic decomposition. J. Symbolic Comput. 66 (2015), 34–69. https://doi.org/10.1016/j.jsc.2014.02.001

    2015 doi

  30. [39]

    G. Moroz. 2021. New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. arXiv:2106.02505

    2021 arXiv

  31. [40]

    Obreshkoff

    N. Obreshkoff. 2003. Zeros of polynomials. Marin Drinov Academic Publishing House, Sofia, Bulgaria. Translation from the Bulgarian

    2003

  32. [41]

    Victor Y Pan. 1997. Solving a polynomial equation: some history and recent progress. SIAM review 39, 2 (1997), 187–220. https: //doi.org/10.1137/S0036144595288554

    1997 doi

  33. [42]

    Victor Y. Pan. 2000. Approximating complex polynomial zeros: modified Weyl’s quadtree construction and improved Newton’s iteration. J. Complexity 16, 1 (2000), 213–264. https://doi.org/10.1006/jcom.1999.0532 Real computation and complexity (Schloss Dagstuhl, 1998)

    2000

  34. [43]

    Victor Y. Pan. 2002. Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding. J. Symbolic Comput. 33, 5 (2002), 701–733. https://doi.org/10.1006/jsco.2002.0531 Computer algebra (London, ON, 2001)

    2002

  35. [44]

    Victor Y Pan. 2022. New Progress in Classic Area: Polynomial Root-squaring and Root-finding. arXiv e-prints (2022), arXiv–2206

    2022

  36. [45]

    Victor Y Pan. 2024. Nearly Optimal Black Box Polynomial Root-finders. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3860–3900

    2024

  37. [46]

    Pan and Elias P

    Victor Y. Pan and Elias P. Tsigaridas. 2013. On the Boolean complexity of real root refinement. In ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation . ACM, New York, 299–306. https://doi.org/10.1145/2465506.2465938

    2013

  38. [47]

    Daniel Reischert. 1997. Asymptotically fast computation of subresultants. In Proc.of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC). 233–240

    1997

  39. [48]

    Roughgarden

    T. Roughgarden. 2021. Beyond the Worst-Case Analysis of Algorithms . Cambridge University Press, Cambridge. https://doi.org/10.1017/ 9781108637435

    2021

  40. [49]

    Fabrice Rouillier and Paul Zimmermann. 2004. Efficient isolation of polynomial’s real roots. J. Comput. Appl. Math. 162, 1 (2004), 33–50. https://doi.org/10.1016/j.cam.2003.08.015

    2004 doi

  41. [50]

    Rudelson and R

    M. Rudelson and R. Vershynin. 2008. The Littlewood-Offord problem and invertibility of random matrices. Adv. Math. 218, 2 (2008), 600–633. https://doi.org/10.1016/j.aim.2008.01.010

    2008 doi

  42. [51]

    Rudelson and R

    M. Rudelson and R. Vershynin. 2015. Small ball probabilities for linear images of high-dimensional distributions. Int. Math. Res. Not. IMRN 19 (2015), 9594–9617. https://doi.org/10.1093/imrn/rnu243

    2015 doi

  43. [52]

    Michael Sagraloff. 2014. On the complexity of the Descartes method when using approximate arithmetic. J. Symbolic Comput. 65 (2014), 79–110. https://doi.org/10.1016/j.jsc.2014.01.005

    2014 doi

  44. [53]

    Michael Sagraloff and Kurt Mehlhorn. 2016. Computing real roots of real polynomials. J. Symbolic Comput. 73 (2016), 46–86. https: //doi.org/10.1016/j.jsc.2015.03.004

    2016 doi

  45. [54]

    Michael Sagraloff and Chee K. Yap. 2011. A simple but exact and efficient algorithm for complex root isolation. InISSAC 2011—Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation . ACM, New York, 353–360. https://doi.org/10.1145/1993886. 1993938

    2011 doi

  46. [55]

    Arnold Schönhage. 1982. The Fundamental Theorem of Algebra in Terms of Computational Complexity. Manuscript. Univ. of Tübingen, Germany

    1982

  47. [56]

    Vikram Sharma. 2008. Complexity of real root isolation using continued fractions. Theoret. Comput. Sci. 409, 2 (2008), 292–310. https://doi.org/10.1016/j.tcs.2008.09.017

    2008 doi

  48. [57]

    Daniel A Spielman and Shang-Hua Teng. 2004. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) 51, 3 (2004), 385–463

    2004

  49. [58]

    PARI/GP version 2.11.2

    The PARI Group 2019. PARI/GP version 2.11.2. The PARI Group, Univ. Bordeaux. available from http://pari.math.u-bordeaux.fr/

    2019

  50. [59]

    E. C. Titchmarsh. 1939. The theory of functions (second ed.). Oxford University Press, Oxford. x+454 pages. Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms • 27

    1939

  51. [60]

    Tonelli-Cueto and E

    J. Tonelli-Cueto and E. Tsigaridas. 2020. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces. In Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (Kalamata, Greece) (ISSAC ’20). Association for Computing Machinery, ...

    2020

  52. [61]

    Tonelli-Cueto and E

    J. Tonelli-Cueto and E. Tsigaridas. 2021. Condition Numbers for the Cube. I: Univariate Polynomials and Hypersurfaces. To appear in the special issue of the Journal of Symbolic Computation for ISSAC 2020. Available at arXiv:2006.04423

    2021 arXiv

  53. [62]

    Lloyd N Trefethen. 1992. The definition of numerical analysis . Technical Report. Cornell University

    1992

  54. [63]

    Elias Tsigaridas. 2016. SLV: a software for real root isolation. ACM Commun. Comput. Algebra 50, 3 (2016), 117–120

    2016

  55. [64]

    Tsigaridas and Ioannis Z

    Elias P. Tsigaridas and Ioannis Z. Emiris. 2008. On the complexity of real root isolation using continued fractions. Theoret. Comput. Sci. 392, 1-3 (2008), 158–173. https://doi.org/10.1016/j.tcs.2007.10.010

    2008 doi

  56. [65]

    A. M. Turing. 1948. Rounding-off errors in matrix processes. Quart. J. Mech. Appl. Math. 1 (1948), 287–308. https://doi.org/10.1093/ qjmam/1.1.287

    1948

  57. [66]

    Joachim von zur Gathen and Jürgen Gerhard. 2003. Modern computer algebra (second ed.). Cambridge University Press, Cambridge. xiv+785 pages

    2003

  58. [67]

    J. H. Wilkinson. 1971. Some comments from a numerical analyst. J. Assoc. Comput. Mach. 18 (1971), 137–147. https://doi.org/10.1145/ 321637.321638

    1971

  59. [68]

    Chee-Keng Yap et al. 2000. Fundamental problems of algorithmic algebra . Vol. 49. Oxford University Press Oxford. Received ????; revised ????; accepted ????

    2000

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.