The focus of my research is the theory of algorithmic randomness. My overall goals in this work are to understand the various roles that randomness plays in mathematical, computational, and statistical practice; to identify formal limitations to the task of defining randomness, manifested in artifacts of definitions of randomness that yield new instances of incompleteness, undecidability, and independence results; and to determine both the extent to which commonly-held intuitions about the concept of randomness are illuminated by the theory of algorithmic randomness and the extent to which these intuitions are challenged by the theory.

Here is a current list of my papers that are either published or submitted for publication:

• Randomness for computable measures and initial segment complexity (with Rupert Hölzl). Submitted.

Abstract

In this paper, we study the various growth rates of proper sequences. In particular, we show the initial segment complexity of a proper sequence is bounded from below by a computable function if and only if is random with respect to some computable, continuous measure. We also identify a global computable lower bound for the initial segment complexity of all -random sequences for a computable, continuous measure . Furthermore we show that there are proper sequences with extremely slow-growing initial segment complexity, i.e., there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. Lastly, we prove various facts about such the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on , namely diminutive measures and trivial measures.

• The interplay of classes of algorithmically random objects (with Quinn Culver). Accepted for publication in the *Journal of Logic and Analysis*.

Abstract

Our main results are the following. First we answer an open question of Barmapalias, Brodhead, Cenzer, Remmel, and Weber by showing that is a random closed set if and only if it is the set of zeros of a random continuous function on . As a corollary we obtain the result that the collection of random continuous functions on is not closed under composition. Next, we construct a computable measure on the space of measures on such that is a random closed set if and only if is the support of a -random measure. We also establish a correspondence between random closed sets and the random measures studied by Culver in previous work. Lastly, we study the ranges of random continuous functions, showing that the Lebesgue measure of the range of a random continuous function is always contained in (0,1).

• On analogues of the Church-Turing thesis in algorithmic randomness. Accepted for publication in the *Review of Symbolic Logic*.

Abstract

• Deep classes (with Laurent Bienvenu). Accepted for publication the *Bulletin of Symbolic Logic*.

Abstract

We prove a number of basic results about depth, negligibility, and a variant of negligibility that we call -negligibility. We also provide a number of examples of deep classes that occur naturally in computability theory and algorithmic randomness. We also study deep classes in the context of mass problems, we examine the relationship between deep classes and certain lowness notions in algorithmic randomness, and establish a relationship between members of deep classes and the amount of mutual information with Chaitin's .

• Randomness and semi-measures (with Laurent Bienvenu, Rupert Hölzl, and Paul Shafer). Forthcoming in the *Notre Dame Journal of Formal Logic*.

Abstract

• Algorithmically random functions and effective capacities (with Doug Cenzer). *Theory and Applications of Models of Computation*, 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings (Lecture Notes in Computer Science), pp. 23-37, 2015.

Abstract

*partial*Martin-Löf random function on and give a family of online partial random functions the ranges of which are precisely the random closed sets introduced by Barmpalias, Brodhead, Cenzer, Dashti, and Weber.

• Demuth's path to algorithmic randomness (with André Nies and Antonín Kučera). *The Bulletin of Symbolic Logic*, 21(3), September 2015, pp. 270-305.

Abstract

In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth's work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth's independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth's work.

• Trivial measures are not so trivial. * Theory of Computing Systems*, Volume 56 Issue 3, April 2015.

Abstract

*trivial*measures, where a measure on is trivial if the support of consists of a countable collection of sequences. In this article, it is shown that there is much more structure to trivial computable measures than has been previously suspected.

• Kolmogorov on the role of randomness in probability theory. *Mathematical Structures in Computer Science*, invited publication in special issue, “Developments of the concepts of randomness, statistic, and probability,” 24, June 2014.

Abstract

*applicability problem*. In particular, I highlight the role of randomness in Kolmogorov's account, and I argue that this role differs significantly from the role that randomness plays in von Mises' account.

• Strong reductions in effective randomness (with Laurent Bienvenu), *Theoretical Computer Science*, Vol. 459, November 2012, pp. 55-68.

Abstract

Here is a list of projects that are currently in progress:

• The interplay between Demuth randomness and effective genericity (with Laurent Bienvenu).

• The V'yugin algebra of non-negligible classes (with Rupert Hölzl).

• Random members of a class (with Douglas Cenzer).

• Rank and randomness (with Douglas Cenzer and Rupert Hölzl).

You can read my dissertation here:

• Mathematical and philosophical perspectives on algorithmic randomness. Doctoral dissertation, University of Notre Dame, 2012.

Abstract

In the philosophical portion of my dissertation, I consider the problem of producing a correct definition of randomness, as introduced in Chapter 7. Some have claimed that one definition of randomness in particular, Martin-Löf randomness, captures the so-called intuitive conception of randomness, a claim known as the Martin-Löf-Chaitin Thesis. However, as some have also offered alternative definitions as capturing our intuitions of randomness, giving rise to the problem of determining which, if any, of these definitions is correct.

Prior to evaluating the Martin-Löf-Chaitin Thesis and related randomness-theoretic theses, the historical Chapters 8 and 9 discuss two roles of definitions of randomness, both of which motivated much early work in the development of algorithmic randomness: the resolutory role of randomness (as part of Richard von Mises’ frequentist approach to probability), which is successfully filled by a definition of randomness that allows for the solution of problems in von Mises’ theory of probability, and the exemplary role of randomness (identified by the probability theorist Jean Ville), which is successfully filled by a definition of randomness that counts as random those sequences that exemplify the properties typically held by sequences chosen at random.

In Chapter 10, I lay out the status of the Martin-Löf-Chaitin Thesis, discussing the evidence that has been offered in support of it, as well as the arguments that have been raised against it. In Chapter 11, I argue that the advocate of a claim like the Martin-Löf-Chaitin Thesis faces what I call the Justificatory Challenge: she must present a precise account of the so-called intuitive conception of randomness, so as to justify the claim that her preferred definition of randomness is the correct one while blocking the claim of correctness made on behalf of alternative definitions of randomness. Lastly, in Chapter 12, I present two further roles for definitions of randomness to play (beyond those discussed in Chapters 8 and 9), which I call the calibrative role of randomness and the limitative role of randomness, both of which can be successfully filled by multiple definitions of randomness. Definitions filling the calibrative role allow us to calibrate the level of randomness necessary and sufficient for certain “almost-everywhere" results in classical mathematics to hold, while definitions filling the limitative role illuminate a phenomenon known as the indefinite contractibility of the notion of randomness. Moreover, I argue that in light of the fact that many definitions can successfully fill these two roles, we should accept what we call the No-Thesis Thesis: there is no definition of randomness that (i) yields a well-defined, definite collection of random sequences and (ii) captures everything that mathematicians have taken to be significant about the concept of randomness.