Skip to main content

On the query complexity of real functionals

Férée, Hugo, Hoyrup, Mathieu, Gomaa, Walid (2013) On the query complexity of real functionals. In: 28th ACM/IEEE Symposium on Logic in Computer Science. Logic in Computer Science (LICS), 2013 28th Annual IEEE/ACM Symposium on. . pp. 103-112. IEEE ISBN 978-1-4799-0413-6. (doi:10.1109/LICS.2013.15) (KAR id:64996)

PDF Author's Accepted Manuscript
Language: English
Download (363kB) Preview
[thumbnail of query_complexity.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format
Official URL
http://dx.doi.org/10.1109/LICS.2013.15

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.

Item Type: Conference or workshop item (Paper)
DOI/Identification number: 10.1109/LICS.2013.15
Uncontrolled keywords: norm, Computable analysis, computational complexity, oracle Turing machine, polynomial time computable functional
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Hugo Feree
Date Deposited: 05 Dec 2017 13:12 UTC
Last Modified: 16 Nov 2021 10:24 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/64996 (The current URI for this page, for reference purposes)
  • Depositors only (login required):