On parallel complexity of analytic functions

Ker-I Ko, Fuxiang Yu

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

In this paper, we study the parallel complexity of analytic functions. We investigate the complexity of computing the derivatives, integrals, and zeros of NC or logarithmic-space computable analytic functions, where NC denotes the complexity class of sets acceptable by polynomial-size, polylogarithmic-depth, uniform Boolean circuits. It is shown that the derivatives and integrals of NC (or logarithmic-space) computable analytic functions remain NC (or, respectively, logarithmic-space) computable. We also study the problem of finding all zeros of an NC computable analytic function inside an NC computable Jordan curve, and show that, under a uniformity condition on the function values on the Jordan curve, all zeros can be found in NC. (c) 2013 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)48-57
Number of pages10
JournalTheoretical Computer Science
Volume489
DOIs
StatePublished - 10 Jun 2013

Keywords

  • Complexity; Analytic functions; Logarithmic space; NC; Derivatives; Integration; Zero-finding

Fingerprint Dive into the research topics of 'On parallel complexity of analytic functions'. Together they form a unique fingerprint.

  • Cite this