Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with computable analysis:
TR02-014 | 10th December 2001
Klaus Weihrauch

Computational Complexity on Computable Metric Spaces

Revisions: 1

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

TR05-157 | 10th December 2005
Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

Points on Computable Curves

The ``analyst's traveling salesman theorem'' of geometric
measure theory characterizes those subsets of Euclidean
space that are contained in curves of finite length.
This result, proven for the plane by Jones (1990) and
extended to higher-dimensional Euclidean spaces by
Okikiolu (1991), says that a bounded set $K$ is contained
more >>>

TR14-015 | 24th January 2014
Jack H. Lutz, Neil Lutz

Lines Missing Every Random Point

Revisions: 1

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>

TR14-133 | 15th October 2014
Adam Case, Jack H. Lutz

Mutual Dimension

We define the lower and upper mutual dimensions $mdim(x:y)$ and $Mdim(x:y)$ between any two points $x$ and $y$ in Euclidean space. Intuitively these are the lower and upper densities of the algorithmic information shared by $x$ and $y$. We show that these quantities satisfy the main desiderata for a satisfactory ... more >>>

ISSN 1433-8092 | Imprint