@article{doi:10.1137/0218024,
    Abstract = {Let \$d\\_1 , \cdots ,d\\_n \$ be positive integers. Let \$\mathcal{P}\$ denote the set of systems of polynomials \$f:\mathbb{C}^n \to \mathbb{C}^n \$ that have only finitely many zeros, including those ``at infinity,'' and that satisfy degree \$(f\\_i ) = d\\_i \$ for all i. Let \$0 < \varepsilon \leqq R\$. It is shown for fixed \$d\\_1 , \cdots ,d\\_n \$, that with respect to a certain model of computation, the worst-case computational complexity of obtaining \$\varepsilon \$-approximations to at least those zeros \$\xi \$ satisfying \$|\xi | \leqq R\$ for arbitrary \$f \in \mathcal{P}\$ is \$\Theta (\log \log (({ R / \varepsilon }))\$; that is to say, both upper and lower bounds are proved. An algorithm for proving the upper bound is introduced. The number of operations required by this algorithm is \[O\left[ {n\mathcal{D}^4 (\log \mathcal{D})(\log \log ( { R / \varepsilon } )) + n^2 \mathcal{D}^4 \left( \begin{array}{*{20}c} {1 + \Sigma d\\_i} \\ n \\ \end{array} \right)^4 } \right],\quad {\text{where }}\mathcal{D} = \prod\limits\\_{i = 1}^n {d\\_i .} \]},
    Author = {Renegar, James},
    EPrint = {https://doi.org/10.1137/0218024},
    File = {On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials - 0218024.pdf},
    Journal = {SIAM Journal on Computing},
    Number = {2},
    Pages = {350-370},
    Title = {On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials},
    URL = {https://doi.org/10.1137/0218024},
    Volume = {18},
    Year = {1989},
    bdsk-url-1 = {https://doi.org/10.1137/0218024},
    date-added = {2022-10-22 08:20:52 +0200},
    date-modified = {2022-10-22 08:20:52 +0200},
    doi = {10.1137/0218024}
}

@article{doi:10.1137/0218024, Abstract = {Let \$d\1 , \cdots ,d\_n \$ be positive integers. Let \$\mathcal{P}\$ denote the set of systems of polynomials \$f:\mathbb{C}^n \to \mathbb{C}^n \$ that have only finitely many zeros, including those ``at infinity,'' and that satisfy degree \$(f\_i ) = d\_i \$ for all i. Let \$0 < \varepsilon \leqq R\$. It is shown for fixed \$d\_1 , \cdots ,d\_n \$, that with respect to a certain model of computation, the worst-case computational complexity of obtaining \$\varepsilon \$-approximations to at least those zeros \$\xi \$ satisfying \$|\xi | \leqq R\$ for arbitrary \$f \in \mathcal{P}\$ is \$\Theta (\log \log (({ R / \varepsilon }))\$; that is to say, both upper and lower bounds are proved. An algorithm for proving the upper bound is introduced. The number of operations required by this algorithm is [O\left[ {n\mathcal{D}^4 (\log \mathcal{D})(\log \log ( { R / \varepsilon } )) + n^2 \mathcal{D}^4 \left( \begin{array}{*{20}c} {1 + \Sigma d\_i} \ n \ \end{array} \right)^4 } \right],\quad {\text{where }}\mathcal{D} = \prod\limits\, Author = {Renegar, James}, EPrint = {https://doi.org/10.1137/0218024}, File = {On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials - 0218024.pdf}, Journal = {SIAM Journal on Computing}, Number = {2}, Pages = {350-370}, Title = {On the Worst-Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials}, URL = {https://doi.org/10.1137/0218024}, Volume = {18}, Year = {1989}, bdsk-url-1 = {https://doi.org/10.1137/0218024}, date-added = {2022-10-22 08:20:52 +0200}, date-modified = {2022-10-22 08:20:52 +0200}, doi = {10.1137/0218024} }}^n {d\_i .} ]