Abstract: We show that for any constant d, complex roots of degree d univariate rational (or Gaussian rational) polynomials---given by a list of coefficients in binary---can be computed to a given accuracy by a uniform TC^0 algorithm (a uniform family of constant-depth polynomial-size threshold circuits). The basic idea is to compute the inverse function of the polynomial by a power series. We also discuss an application to the theory VTC^0 of bounded arithmetic.
Recommendations
Cites work
- scientific article; zbMATH DE number 3161517 (Why is no real title available?)
- scientific article; zbMATH DE number 3613366 (Why is no real title available?)
- scientific article; zbMATH DE number 1351078 (Why is no real title available?)
- scientific article; zbMATH DE number 3443655 (Why is no real title available?)
- scientific article; zbMATH DE number 770106 (Why is no real title available?)
- scientific article; zbMATH DE number 1446863 (Why is no real title available?)
- scientific article; zbMATH DE number 3214534 (Why is no real title available?)
- scientific article; zbMATH DE number 2196509 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- scientific article; zbMATH DE number 3057883 (Why is no real title available?)
- A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots
- A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
- An efficient algorithm for the complex roots problem
- Constant Depth Reducibility
- Division in logspace-uniform NC
- Efficient threshold circuits for power series
- Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
- Log Depth Circuits for Division and Related Problems
- Logarithmic Depth Circuits for Algebraic Functions
- Logical foundations of proof complexity
- Majority Gate Networks
- Numerical recipes. The art of scientific computing.
- On Threshold Circuits and Polynomial Computation
- On uniform circuit complexity
- On uniformity within \(NC^ 1\)
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- Parallel computation with threshold functions
- Solving a Polynomial Equation: Some History and Recent Progress
- Specified precision polynomial root isolation is in NC
- Threshold circuits of bounded depth
- Uniform constant-depth threshold circuits for division and iterated multiplication.
Cited in
(5)- Computing rational radical sums in uniform \(\mathrm{TC}^0\)
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\)
- On the complexity of the clone membership problem
- Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication
This page was built for publication: Root finding with threshold circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q690451)
