The development of algorithmic fractal dimensions in this century has had many fruitful
interactions with geometric measure theory, especially fractal geometry in Euclidean spaces …

We show that if a real x∈ 2ω is strongly Hausdorff Hh-random, where h is a dimension
function corresponding to a convex order, then it is also random for a continuous probability …

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the
structure of complexity classes, but then interesting connections of effective dimension with …

The study of mass problems and Muchnik degrees was originally motivated by Kolmogorov's
non-rigorous 1932 interpretation of intuitionism as a calculus of problems. The purpose of …

We apply recent results on extracting randomness from independent sources to “extract”
Kolmogorov complexity. For any α, ε> 0, given a string x with K (x)> α| x|, we show how to …

This paper develops new relationships between resource-bounded dimension, entropy
rates, and compression. New tools for calculating dimensions are given and used to improve …

We apply results on extracting randomness from independent sources to “extract”
Kolmogorov complexity. For any α, ϵ> 0, given a string x with K (x)> α| x|, we show how to …

In the work of Nash et al.(2005) have raised the question whether a logic L les, already
introduced by Gurevich in 1988, captures polynomial time, and they give a reformulation of …

This work solves an open problem regarding the rate of time-bounded Kolmogorov
complexity and polynomial-time dimension, conditioned on a hardness assumption …

We introduce the concept of effective dimension for a wide class of metric spaces whose
metric is not necessarily based on a measure. Effective dimension was defined by Lutz (Inf …