"Complexity Theory of (Functions on) Compact Metric Spaces"
(joint work with Akitoshi Kawamura and Florian Steinberg)
We promote the theory of computational complexity on metric spaces: as natural common generalization of
(i) the classical discrete setting of integers, binary strings, graphs etc. as well as of (ii) the
bit-complexity theory on real numbers and functions according to Friedman, Ko (1982ff), Cook, Braverman
et al.; as (iii) resource-bounded refinement of the theories of computability on, and representations of,
continuous universes by Pour-El&Richards (1989) and Weihrauch (1993ff); and as (iv) computational
perspective on quantitative concepts from classical Analysis: Our main results relate (i.e. upper and
lower bound) Kolmogorov's entropy of a compact metric space $X$ polynomially to the uniform relativized
complexity of approximating various families of continuous functions on $X$. The upper bounds are
attained by carefully crafted oracles and bit-cost analyses of algorithms perusing them. They all employ
the same representation (i.e. encoding, as infinite binary sequences, of the elements) of such spaces,
which thus may be of own interest. The lower bounds adapt adversary arguments from unit-cost
Information-Based Complexity to the bit model. They extend to, and indicate perhaps surprising
limitations even of, encodings via binary string functions (rather than sequences) as introduced by
Kawamura&Cook (SToC'2010,\S3.4). These insights offer some guidance towards suitable notions of
complexity for higher types.