[Colloquium] Talk by Jack H. Lutz on Wednesday, May 7, 2003

[Margery Ishmael]

----------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Wednesday, May 7, 2003 at 2:30 pm in Ryerson 251

-----------------------------------------------------------------------------

Speaker: Jack H. Lutz

From: Iowa State University
http://www.cs.iastate.edu/~lutz/

Title: "Randomness and Dimension"

Abstract:
The two most important notions of fractal dimension are {\it Hausdorff 
dimension}, developed by Hausdorff (1919), and {\it packing dimension}, 
developed independently by Tricot (1982) and Sullivan (1984). Both 
dimensions have the mathematical advantage of being defined from measures, 
and both have yielded extensive applications in fractal geometry and 
dynamical systems.

In 2000, the speaker proved a simple characterization of Hausdorff 
dimension in terms of {\it gales}, which are betting strategies that 
generalize martingales. Imposing various computability and complexity 
constraints on these gales produces a spectrum of effective versions of 
Hausdorff dimension, including constructive, computable, polynomial- space, 
polynomial-time, and finite-state dimensions. Work by several investigators 
has already used these effective dimensions to shed light on a variety of 
topics in theoretical computer science, including algorithmic information 
theory, computational complexity, prediction, and data compression. 
Constructive dimension has also been discretized, assigning a dimension 
dim(x) to each finite, binary string x in a way that arises naturally from 
Hausdorff and constructive dimensions and gives the unexpected 
characterization K(x) = |x|*dim(x) +/- O(1) of Kolmogorov complexity.

Very recent work by Athreya, Hitchcock, Mayordomo and the speaker shows 
that packing dimension -- previously thought to be much more complex than 
Hausdorff dimension -- admits a gale characterization that is an exact dual 
of that of Hausdorff dimension. This characterization leads to a spectrum 
of effective {\it strong} dimensions that are dual to the above effective 
dimensions and have a growing variety of applications.

This talk surveys these developments, with particular attention to the 
dimensions and strong dimensions of random objects. No prior knowledge of 
fractal dimensions will be assumed.

*The talk will be followed by refreshments in Ryerson 255*

Host: Stuart Kurtz


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-