On the Computational Complexity of Best L1-approximation

Mathematical Logic Quarterly 48 (S1):66-77 (2002)
  Copy   BIBTEX

Abstract

It is well known that for a given continuous function f : [0, 1] → ℝ and a number n there exists a unique polynomial pn ∈ Pn which best L1-approximates f. We establish the first upper bound on the complexity of the sequence n∈ ℕ, assuming f is polynomial-time computable. Our complexity analysis makes essential use of the modulus of uniqueness for L1-approximation presented in [13]

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 102,007

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Proof mining in L1-approximation.Ulrich Kohlenbach & Paulo Oliva - 2003 - Annals of Pure and Applied Logic 121 (1):1-38.
Computable Riesz representation for the dual of C [0; 1].Hong Lu & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4):415-430.
Lp -Computability.Ning Zhong & Bing-Yu Zhang - 1999 - Mathematical Logic Quarterly 45 (4):449-456.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Derivatives of Computable Functions.Ning Zhong - 1998 - Mathematical Logic Quarterly 44 (3):304-316.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.

Analytics

Added to PP
2013-12-01

Downloads
71 (#301,918)

6 months
6 (#818,268)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Proof mining in L1-approximation.Ulrich Kohlenbach & Paulo Oliva - 2003 - Annals of Pure and Applied Logic 121 (1):1-38.

Add more citations