Bounded time computation on metric spaces and Banach spaces

Matthias Schröder; Florian Steinberg

doi:10.1109/LICS.2017.8005139

2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

Bounded time computation on metric spaces and Banach spaces

Year: 2017, Pages: 1-12

DOI Bookmark: 10.1109/LICS.2017.8005139

Authors

Matthias Schröder, Technische Universität Darmstadt, Schloßgartenstraße 7, 64289, Germany
Florian Steinberg, Technische Universität Darmstadt, Schloßgartenstraße 7, 64289, Germany

Abstract

We extend Kawamura and Cook's framework for computational complexity for operators in analysis. This model is based on second-order complexity theory for functionals on the Baire space, which is lifted to metric spaces via representations. Time is measured in the length of the input encodings and the output precision.

Like what you’re reading?

Already a member?

Get this article FREE with a new membership!

A Light Metric Spanner
2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)
An eigenvalue-based pivot selection strategy for improving search efficiency in metric spaces
2016 International Conference on Big Data and Smart Computing (BigComp)
Complexity Theory of (Functions on) Compact Metric Spaces
2016 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
Some New Fuzzy Fixed Point Theorems for Fuzzy Contractive Mappings in Hausdorff Fuzzy Metric Spaces
2018 International Conference on Control, Artificial Intelligence, Robotics & Optimization (ICCAIRO)
Impact of Categorical Variable Encodings on Bayesian Optimization Performance
2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI)
Smoothness of Spaces in Finite Element Methods
2018 5th International Conference on Mathematics and Computers in Sciences and Industry (MCSI)
Some results in cone b -metric spaces over Banach algebras
2020 International Symposium on Computer Engineering and Intelligent Communications (ISCEIC)
HST+: An Efficient Index for Embedding Arbitrary Metric Spaces
2021 IEEE 37th International Conference on Data Engineering (ICDE)
On Generalized Metric Spaces for the Simply Typed Lambda-Calculus
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
DIMS: Distributed Index for Similarity Search in Metric Spaces
IEEE Transactions on Knowledge & Data Engineering

Bounded time computation on metric spaces and Banach spaces

Authors

Abstract

Related Articles