Algorithmic Randomness Summer School
Tutorial Speakers
Andre Nies
University of Auckland
Jan Reimann
University of Berkeley
John Hitchcock
University of Wyoming
Summer School Poster
Download
PDF
June 9 - June 19, 2008
Gainesville, Florida
Introduction
This Summer School for graduate students (and faculty) is an important component of the the Focused Research Group on Algorithmic Randomness, which is a collaborative effort by researchers at many sites who bring ideas from recursion theory, complexity theory, and other specialties to bear on questions about algorithmic randomness.
Important background notions include the ideas of Kolmogorov complexity and Martin-Lof randomness, which hae separately and jointly received large amounts of attention, and which come together in many of the examples and problems described in this proposal. Issues being studied include relationships between Martin-Lof random sets and Hausdorff dimension or other measures of dimension, methods for extracting randomness from a semi-random source of data, dimensions and other properties of complexity classes of strings, distinctive properties of sets with low Kolmogorov complexity, and relationships between algorithmic randomness and reverse mathematics, which seeks to understand the axiomatic strength required by particular theories.
The forms of randomness studied by this group of researchers are based on some appealing ideas regarding infinite strings, such as the record of an infinitely repeated series of coin tosses. Intuitively, the Kolmogorov complexity of a binary string like the record of heads and tails from coin tosses is the length of the shortest definitive description of the string. Digitization methods for voice and picture transmission take advantage of the regularity and repetition in typical voice signals or digitized images, using much less space or time to record the sound or image data than might seem necessary. From the point of view of Kolmogorov complexity, a genuinely random binary string is probably its own shortest description, or nearly so. Some of the problems studied by this research group seek to establish properties of subsets of strings that have the same complexity, such as their dimension.
