Root finding with threshold circuits

DOI10.1016/J.TCS.2012.09.001zbMATH Open1282.68116arXiv1112.3925OpenAlexW2121824896MaRDI QIDQ690451FDOQ690451

Authors: Emil Jeřábek 

Publication date: 27 November 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Numerical recipes. The art of scientific computing.
• Title not available (Why is that?)
• Title not available (Why is that?)
• On uniform circuit complexity
• On uniformity within \(NC^ 1\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logical foundations of proof complexity
• Parallel computation with threshold functions
• Threshold circuits of bounded depth
• Title not available (Why is that?)
• Solving a Polynomial Equation: Some History and Recent Progress
• Title not available (Why is that?)
• Title not available (Why is that?)
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Log Depth Circuits for Division and Related Problems
• Majority Gate Networks
• Specified precision polynomial root isolation is in NC
• Division in logspace-uniform NC
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• Title not available (Why is that?)
• A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
• Constant Depth Reducibility
• Logarithmic Depth Circuits for Algebraic Functions
• An efficient algorithm for the complex roots problem
• On Threshold Circuits and Polynomial Computation
• Efficient threshold circuits for power series
• A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots

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)