1. Independence, Relative Randomness, and PA Degrees [pdf]
    (with Adam Day)
    To appear in Notre Dame Journal of Formal Logic
    Abstract: We study pairs of reals that are mutually Martin-L\"{o}f random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen's Theorem holds for non-computable probability measures, too. We study, for a given real A, the \emph{independence spectrum} of A, the set of all B so that there exists a probability measure \mu so that \mu\{A,B\} = 0 and (A,B) is \mu x \mu-random. We prove that if A is c.e., then no \Delta^0_2 set is in the independence spectrum of A. We obtain applications of this fact to PA degrees. In particular, we show that if A is c.e.\ and P is of PA degree so that P \not\ge_{\T} A, then A \oplus P \geqT \emptyset'.

  2. Randomness for continuous measures [pdf]
    (with Theodore A. Slaman)
    Revised Draft
    Abstract: We study randomness with respect to arbitrary (that is, not necessarily computable) continuous measures. We show that for every n, the set NCR_n of reals that are not random with respect to a continuous probability measure is countable. The proof uses Borel determinacy and Kumabe-Slaman forcing. Furthermore, we show that for every k, the statement "For all n, NCR_n is countable." cannot be proven in ZFC(-) + "There exists k iterates of the power set of ω", where ZFC(-) denotes Zermelo-Fraenkel set theory with choice minus the power set axiom. The proof exhibits a model L_β such that NCR_n is cofinal in the Turing degrees of L_β. (L_β is a level of Goedel's constructible hierarchy.)

  3. Measures and their random reals [pdf]
    (with Theodore A. Slaman)
    To appear in Transactions of the AMS
    Abstract: We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-recursive real is non-trivially random with respect to some measure. The probability measures constructed in the proof may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for a continuous measure can be found throughout the hyperarithmetical hierarchy.

  4. Probability measures and effective randomness [pdf]
    (with Theodore A. Slaman)
    To appear in: 13th International Congress of Logic Methodology and Philosophy of Science, Beijing, 2007
    Abstract: This is a survey of recent work by the authors on randomness for continuous measures.

  5. Effectively closed classes of measures and randomness [pdf]
    Annals of Pure and Applied Logic, 156(1), pp 170--182, 2008.
    Abstract: We show that if a real $x \in \Cant$ is strongly Hausdorff $\Hm{h}$-random, where $h$ is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure $\mu$ such that the $\mu$-measure of the basic open cylinders shrinks according to $h$. The proof uses a new method to construct measures, based on effective (partial) continuous transformations and a basis theorem for $\Pi^0_1$-classes applied to closed sets of probability measures. We use the main result to give a new proof of Frostman's Lemma, to derive a collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostman's Theorem.

  6. Randomness beyond Lebesgue measure [pdf]
    Logic Colloquium 06, Nijmegen. To appear.
    Abstract: Much of the recent research on algorithmic randomness has focused on randomness for Lebesgue measure. While, from a computability theoretic point of view, the picture remains unchanged if one passes to arbitrary computable measures, interesting phenomena occur if one studies the the set of reals which are random for an arbitrary measure on Cantor space. This paper tries to give a survey of the research that has been done on randomness for non-Lebesgue measures.

  7. A lower cone in the wtt degrees of non-integral effective dimension [pdf]
    (with Andre Nies)
    Proceedings of IMS workshop on Computational Prospects of Infinity, Part II, National University of Singapore, World Scientific, 2008.
    Abstract: For any rational number r, we show that there exists a set A (weak truth-table reducible to the halting problem) such that any set B weak truth-table reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wtt-lower cone of effective dimension r.

  8. Schnorr dimension [pdf]
    (with Rodney G. Downey and Wolfgang Merkle)
    Mathematical Structures in Computer Science, 16(5), pp 789-811, 2006.
    (an earlier version appeared in: Computability in Europe, LNCS 3526, pp. 96--105, Springer, 2005)
    Abstract: Following Lutz's approach to effective (constructive) dimension, we define a notion of dimension for individual sequences based on Schnorr's concept(s) of randomness. In contrast to computable randomness and Schnorr randomness, the dimension concepts defined via computable martingales and Schnorr tests coincide, i.e.\ the Schnorr Hausdorff dimension of a sequence always equals its computable Hausdorff dimension. Furthermore, we give a machine characterization of Schnorr dimension, based on prefix-free machines whose domain has computable measure. Finally, we show that there exist computably enumerable sets which are Schnorr (computably) irregular: while every c.e. set has Schnorr Hausdorff dimension 0 there are c.e. sets of computable packing dimension 1, a property impossible in the case of effective (constructive) dimension, due to Barzdins' Theorem. In fact, we prove that every hyperimmune Turing degree contains a set of computable packing dimension 1.

  9. On hierarchies of randomness tests [pdf]
    (with Frank Stephan)
    Mathematical Logic in Asia, Proceedings of the 9th Asian Logic Conference, Novosibirsk, World Scientific Publishing, 2006
    Abstract: It is well known that Martin-Löf randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Löf and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki [2002] and Calude, Staiger and Terwijn [2005] studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper hierarchy of randomness notions, namely for any r of the form r(x) = 2^(-|x|s) with s being a rational number strictly between 0 and 1, the Martin-Löf r-tests are strictly weaker than Solovay r-tests which in turn are strictly weaker than strong Martin-L\"of r-tests. These results also hold for a more general class of r introduced as unbounded premeasures.

  10. On selection functions that do not preserve normality [pdf]
    (with Wolfgang Merkle)
    Theory of Computing Systems 39(5):685-697, 2006.
    (an earlier version appeared in: Mathematical foundations of computer science 2003, LNCS 2747, pp. 602--611, Springer, 2003)
    Abstract: The sequence selected from a sequence R(0)R(1)... by a language L is the subsequence of R that contains exactly the bits R(n+1) such that the prefix R(0)...R(n) is in L. By a result of Agafonoff, a sequence is normal if and only if any subsequence selected by a regular language is again normal. Kamae and Weiss and others have raised the question of how complex a language must be such that selecting according to the language does not preserve normality. We show that there are such languages that are only slightly more complicated than regular ones, namely, normality is preserved neither by deterministic one-counter languages nor by linear languages. In fact, for both types of languages it is possible to select a constant sequence from a normal one.

  11. Kolmogorov-Loveland randomness and stochasticity [pdf]
    (with Woflgang Merkle, Joseph Miller, André Nies, and Frank Stephan)
    Annals of Pure and Applied Logic, 138(1-3):183--210, 2005.
    (an earlier version appeared in: STACS 2005 (Stuttgart), LNCS 3404, pp. 422--433, Springer, 2005)
    Abstract: An infinite binary sequence X is Kolmogorov-Loveland (or KL) random if there is no computable non-monotonic betting strategy that succeeds on X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence. One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. However, this does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n-g(n). Again, the latter property does not characterize KL-randomness; we construct a left-r.e.\ sequence that has this property but is not KL-stochastic, in fact, is not even Mises-Wald-Church stochastic. Furthermore, we construct a non-empty effectively closed class of KL-stochastic sequences that are not weakly 1-random. Another result asserts that every KL-stochastic sequence has effective dimension 1. This improves on a result by Muchnik.

  12. Effective Hausdorff dimension [pdf]
    (with Frank Stephan)
    Baaz, Friedman, Krajicek (eds.), Logic Colloquium '01, Association for Symbolic Logic, 2005.
    Abstract: We continue the study of effective Hausdorff dimension as it was initiated by Lutz. Whereas he uses a generalization of martingales on the Cantor space to introduce this notion we give a characterization in terms of effective s-dimensional Hausdorff measures, similar to the effectivization of Lebesgue measure by Martin-Löf. It turns out that effective Hausdorff dimension allows to classify sequences according to their `degree' of algorithmic randomness, i.e., their algorithmic density of information. Earlier the works of Staiger and Ryabko showed a deep connection between Kolmogorov complexity and Hausdorff dimension. We further develop this relationship and use it to give effective versions of some important properties of (classical) Hausdorff dimension. Finally, we determine the effective dimension of some objects arising in the context of computability theory, such as degrees and spans.

  13. Computability and Fractal Dimension[pdf]
    Doctoral Dissertation, Universität Heidelberg, 2004.
     
  14. Almost complete sets [pdf]
    (with Klaus Ambos-Spies, Wolfgang Merkle and Sebastiaan A. Terwijn)
    Theoretical Compter Science 306:177-194, 2003.
    (an earlier version appeared in: STACS 2000 (Lille), LNCS 1770, pp. 419--430, Springer, 2000)
    Abstract: We show that there is a set which is almost complete but not complete under polynomial-time many-one reductions for the class E. Here a set A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not r-reduce to A has measure 0 in C in the sense of Lutz's resource-bounded measure theory. We also show that the almost complete sets for E under polynomial-time bounded one-one length-increasing reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP.

  15. Hausdorff dimension in exponential time [pdf]
    (with Klaus Ambos-Spies, Wolfgang Merkle, and Frank Stephan)
    Proc. 16th Conference on Computational Complexity, pp. 210--217, IEEE Computer Society, 2001.
    Abstract:In this paper we investigate effective versions of Hausdorff dimension which have been recently introduced by Lutz. We focus on dimension in the class E of sets computable in linear exponential time. We determine the dimension of various classes related to fundamental structural properties including different types of autoreducibility and immunity. By a new general invariance theorem for resource-bounded dimension we show that the class of p-m-complete sets for E has dimension 1 in E. Moreover, we show that there are p-m-lower spans in E of dimension H(s) for any rational s between 0 and 1, where H(s) is the binary entropy function. This leads to a new general completeness notion for E that properly extends Lutz's concept of weak completeness. Finally we characterize resource-bounded dimension in terms of martingales with restricted betting ratios and in terms of prediction functions.

  16. Effective Baire category concepts [pdf]
    (with Klaus Ambos-Spies)
    Proc. Sixth Asian Logic Conference 1996, pp. 13--29, Singapore University Press, 1998.
    Abstract: Mehlhorn [1973] introduced an effective Baire category concept designed for measuring the size of computable sets. This concept is based on effective extension functions. By considering partial extension functions, we introduce a stronger concept. Similar resource-bounded concepts have been previously introduced by Ambos-Spies et al. [1988] and Ambos-Spies [1996]. By defining a new variant of the Banach-Mazur game, we give a game theoretical characterization of our category concept.

  17. Topologische Spiele und resourcenbeschränkte Baire-Kategorie [pdf]
    Diploma Thesis, Universität Heidelberg, 1997.