IRFP: Randomness Preservation and Randomness Extraction

Porter Christopher P, Notre Dame IN

Investigators

Abstract

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).