0382374 - MÚ 2013 RIV NL eng J - Článek v odborném periodiku
Jeřábek, Emil
Root finding with threshold circuits.
Theoretical Computer Science. Roč. 462, Nov 30 (2012), s. 59-69. ISSN 0304-3975. E-ISSN 1879-2294
Grant CEP: GA AV ČR IAA100190902; GA MŠMT(CZ) 1M0545
Institucionální podpora: RVO:67985840
Klíčová slova: root finding * threshold circuit * power series
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 0.489, rok: 2012 ; AIS: 0.574, rok: 2012
Web výsledku:
http://www.sciencedirect.com/science/article/pii/S0304397512008006#DOI: https://doi.org/10.1016/j.tcs.2012.09.001

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.
Trvalý link: http://hdl.handle.net/11104/0215362