The International Research Fellowship Program enables U.S. scientists and engineers to conduct nine to twenty-four months of research abroad. The program's awards provide opportunities for joint research, and the use of unique or complementary facilities, expertise and experimental conditions abroad.

This award will support a twenty-two-month research fellowship by Dr. Christopher P. Porter to work with Dr. Laurent Bienvenu at Université Paris Diderot - Paris 7 in Paris, France.

Algorithmic randomness, a discipline that lies at the intersection of computability theory, probability theory, and information theory, among other disciplines, has received increased attention in recent years. However, a number of important issues concerning the interaction between randomness preservation and randomness extraction, as well as the subject of the rate of randomness extraction, have not been studied adequately from the point of view of algorithmic randomness. Porter and Bienvenu have previously collaborated on the former topic, extending a classical result in Algorithmic Randomness known as Demuth's Theorem and showing several ways that this theorem cannot be extended. The techniques that Porter and Bienvenu have developed merit further investigation, as there is promise for these techniques to have consequences for the study of notions of randomness given in terms of biased probability measures. Moreover, Porter and Bienvenu have a framework in place to investigate the rate of randomness extraction, and they conjecture that they will be able to establish strong connections between Martin-Löf randomness and the average-case extraction rate of certain effectively computable transformations.

Not only will this research contribute to a better understanding of the relationship between algorithmic randomness, randomness extraction, and biased probability measures, but it will also help foster new international collaborations between Porter and various members of Bienvenu's research group (such as his doctoral students Antoine Taveneaux and Benoit Monin), as well as members of other research groups in France with whom Bienvenu is collaborating (most notably Dr. Mathieu Hoyrup in Nancy and Dr. Grégory Lafitte and Dr. Alexander Shen in Montpellier).

Project Report

using the tools of algorithmic randomness. The general idea behind this approach is to study the behavior of algorithmically random sequences under effective transformations (i.e. transformations given by an explicit algorithm). Under certain conditions, randomness is preserved under these transformations, in the sense that if we start with an unbiased random sequence (such as one obtained by tossing a fair coin) and effectively transform it, then an unbiased random sequence can be recovered from this transformed sequence, although the "recovered" sequence is usually not the original unbiased sequence. This latter phase of recovering unbiased randomness from an effectively transformed random sequence, which may itself be a biased random sequence (random with respect to some non-uniform probability distribution) is an instance of randomness extraction. A second goal of the project was to use to the tools of algorithmic randomness to study the power and limitations of probabilistic computation. Roughly, to perform a probabilistic computation, one implements an algorithm with access to a random source of bits. In the context of algorithmic randomness, this is formalized as an effective procedure equipped with an algorithmically random sequence to use as an oracle (i.e. one can consult the values of the random sequence at any point of the computation). In many cases, one can show that the phenomenon of randomness preservation described above does not hold in the context of probabilistic computation: there are probabilistic algorithms that transform some random initial sequence into an output from which no randomness can be effectively recovered. In pursuing these two general goals, Porter (working in collaboration with a number of individuals) established a number of significant results. These results fall under the following projects: (1) In "Randomness and Semi-Measures," carried out jointly with Laurent Bienvenu, Rupert Hölzl, and Paul Shafer, the relationship between randomness and semi-measures is examined, where a semi-measure can be seen as a defective probability measure induced by a specific kind of effective transformation of random sequences. New instances of randomness preservation and its failure are identified. (2) The study, "Deep Pi01 Classes," with Laurent Bienvenu, involves a collection of effectively closed sets of highly structured objects that cannot be successfully produced by any combination of deterministic and probabilistic effective transformations (any such procedure yields a member of a deep class with probability zero). Thus, members of deep classes cannot in general be obtained as the result of an effective transformation of a random sequence. This study has yielded a number of natural examples from computability theory that illustrate a significant limitation of the technique of effectively transforming random sequences. (3) "Strong difference randomness," with Laurent Bienvenu, yields a new class of random sequences in the context of studying a certain class of probabilistic algorithms, recast as effective transformations of random sequences. (4) "Semi-Measures and Non-Negligible Pi01 Classes," with Rupert Hölzl, a technique developed by Vladimir V’yugin in the 1970s is applied to produce, via a fixed probabilistic algorithm, an effectively closed class from which no randomness can be effectively recovered. They prove that not even a very weak notion of randomness can be extracted from this class. (5) The study, "Computable measures and initial segment complexity," with Rupert Hölzl and Wolfgang Merkle, uses the machinery of randomness preservation to study the various growth rates of the initial segment complexity of sequences random with respect to some computable probability measure. (6) In "The interaction between varieties of algorithmically random objects," with Quinn Culver, the machinery of randomness preservation is used to study the relationship between algorithmically random closed sets, algorithmically random continuous functions, and algorithmically random probability measures. (7) "Demuth’s Path to Randomness," written with Antonín Ku?era and André Nies, surveys the contributions of the Czech mathematician Osvald Demuth to the study of algorithmic randomness. Demuth’s work is relatively unknown, but it reveals important connections between algorithmic randomness, classical analysis, and the Markov school of computable analysis.

Agency
National Science Foundation (NSF)
Institute
Office of International and Integrative Activities (IIA)
Application #
1159158
Program Officer
John Tsapogas
Project Start
Project End
Budget Start
2012-09-01
Budget End
2014-08-31
Support Year
Fiscal Year
2011
Total Cost
$141,700
Indirect Cost
Name
Porter Christopher P
Department
Type
DUNS #
City
Notre Dame
State
IN
Country
United States
Zip Code
46556