On parallel complexity of analytic functions

DOI10.1016/J.TCS.2013.04.008MaRDI QIDQ388112zbMATH OpenOpenAlexFDO

Authors Fuxiang Yu, Ker-I Ko

Publication date 19 December 2013

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

Full work available at URL https://doi.org/10.1016/j.tcs.2013.04.008

zbMATH Keywords

complexityintegrationanalytic functionslogarithmic spacederivativesNCzero-finding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Theory and Applications of Models of Computation
• On the Complexity of Polynomial Zeros
• scientific article; zbMATH DE number 4051615
• On the parallel arithmetic complexity of the root-finding problem
• The parallel complexity of function approximation

Cites work

• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 3489473 (Why is no real title available?)
• scientific article; zbMATH DE number 1418967 (Why is no real title available?)
• scientific article; zbMATH DE number 2232802 (Why is no real title available?)
• A Numerical Method for Locating the Zeros of an Analytic Function
• A very hard log-space counting class
• Computational Complexity of Two-Dimensional Regions
• Computational complexity of real functions
• Computing power series in polynomial time
• Computing the zeros of analytic functions
• Division in logspace-uniform NC
• Fast Parallel Matrix Inversion Algorithms
• Fast parallel matrix and GCD computations
• Feasible Real Functions and Arithmetic Circuits
• Log Depth Circuits for Division and Related Problems
• Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
• On initial conditions for the convergence of simultaneous root finding methods
• On the complexity of convex hulls of subsets of the two-dimensional plane
• Real functions, contraction mappings, and P-completeness
• Solution of equations involving analytic functions
• Specified precision polynomial root isolation is in NC
• The computational complexity of maximization and integration
• Uniform computational complexity of the derivatives of \(C^{\infty}\)-functions.
• Weierstrass formula and zero-finding methods

Cited in

(10)

• Computing and Combinatorics
• In Memoriam: Ker-I Ko (1950–2018)
• Uniform computational complexity of the derivatives of \(C^{\infty}\)-functions.
• Problem of checking the functional completeness in the class of piecewise parallel functions
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
• Theory and Applications of Models of Computation
• scientific article; zbMATH DE number 833674 (Why is no real title available?)
• scientific article; zbMATH DE number 3858283 (Why is no real title available?)
• Computing functions with parallel queries to NP
• Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids

This page was built for publication: On parallel complexity of analytic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388112)