id: 06110681
dt: j
an: 06110681
au: Jeřábek, Emil
ti: Root finding with threshold circuits.
so: Theor. Comput. Sci. 462, 59-69 (2012).
py: 2012
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: root finding; threshold circuit; power series; open induction
ci: 
li: doi:10.1016/j.tcs.2012.09.001
ab: Summary: 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.
rv: