Root finding with threshold circuits

DOI10.1016/J.TCS.2012.09.001MaRDI QIDQ690451zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

Publication date 27 November 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.3925

zbMATH Keywords

power seriesroot findingopen inductionthreshold circuit

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

• Low-depth uniform threshold circuits and the bit-complexity of straight line programs
• On Threshold Circuits and Polynomial Computation
• Efficient threshold circuits for power series
• Computing rational radical sums in uniform \(\mathrm{TC}^0\)
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits

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)