On the query complexity of real functionals

Abstract : Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0,1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.
Type de document :
Communication dans un congrès
LICS - 28th ACM/IEEE Symposium on Logic in Computer Science, Jun 2013, New Orleans, United States. pp.103-112, 2013, 〈http://www.computer.org/csdl/proceedings/lics/2013/5020/00/5020a103-abs.html〉. 〈10.1109/LICS.2013.15〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00773653
Contributeur : Mathieu Hoyrup <>
Soumis le : lundi 14 janvier 2013 - 14:32:02
Dernière modification le : jeudi 22 septembre 2016 - 14:31:43
Document(s) archivé(s) le : lundi 15 avril 2013 - 04:02:07

Fichier

preprint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Hugo Férée, Mathieu Hoyrup, Walid Gomaa. On the query complexity of real functionals. LICS - 28th ACM/IEEE Symposium on Logic in Computer Science, Jun 2013, New Orleans, United States. pp.103-112, 2013, 〈http://www.computer.org/csdl/proceedings/lics/2013/5020/00/5020a103-abs.html〉. 〈10.1109/LICS.2013.15〉. 〈hal-00773653〉

Partager

Métriques

Consultations de
la notice

265

Téléchargements du document

149