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]

Categories

Keywords

Reprint years

DOI

10.1002/1521-3870(200210)48:1

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

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

Through your library

My notes

Similar books and articles

Proof mining in L1-approximation.Ulrich Kohlenbach & Paulo Oliva - 2003 - Annals of Pure and Applied Logic 121 (1):1-38.
Approximation Representations for Δ2 Reals.George Barmpalias - 2004 - Archive for Mathematical Logic 43 (8):947-964.
The elementary computable functions over the real numbers: applying two new techniques. [REVIEW]Manuel L. Campagnolo & Kerry Ojakian - 2008 - Archive for Mathematical Logic 46 (7-8):593-627.
Nonrelativistic Strong-Field Photoionization without Making the Dipole Approximation.Yousef I. Salamin - 1998 - Foundations of Physics 28 (4):653-665.
The approximation structure of a computably approximable real.George Barmpalias - 2003 - Journal of Symbolic Logic 68 (3):885-922.
Nonlocality and the Rotating Wave Approximation.A. A. Clerk & J. E. Sipe - 1998 - Foundations of Physics 28 (4):639-651.
Computational complexity on computable metric spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.
Truth approximation via abductive belief change.Gustavo Cevolani - 2013 - Logic Journal of the IGPL 21 (6):999-1016.
On best transitive approximations to simple graphs.Leon Horsten - unknown
Towards an Expanded Epistemology for Approximations.Jeffry L. Ramsey - 1992 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1992:154 - 164.
Interpolation and Approximate Semantic Derivations.Jan Krajíček - 2002 - Mathematical Logic Quarterly 48 (4):602-606.
Max sat approximation beyond the limits of polynomial-time approximation.Evgeny Dantsin, Michael Gavrilovich, Edward A. Hirsch & Boris Konev - 2001 - Annals of Pure and Applied Logic 113 (1-3):81-94.
How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
Aristotle's Physics.Carlo Rovelli - 2013

Analytics

Added to PP
2013-12-01

Downloads
61 (#257,990)

6 months
7 (#425,192)

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

References found in this work

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

Add more references