 |
|
|
Award Abstract #0652569
FRG: Collaborative Research: Algorithmic Randomness
| NSF Org: |
DMS
Division of Mathematical Sciences
|
|
|
| Initial Amendment Date: |
March 30, 2007 |
|
| Latest Amendment Date: |
August 7, 2009 |
|
| Award Number: |
0652569 |
|
| Award Instrument: |
Continuing grant |
|
| Program Manager: |
Tomek Bartoszynski
DMS Division of Mathematical Sciences
MPS Directorate for Mathematical & Physical Sciences
|
|
| Start Date: |
July 1, 2007 |
|
| Expires: |
June 30, 2010 (Estimated) |
|
| Awarded Amount to Date: |
$30000 |
|
| Investigator(s): |
Jack Lutz lutz@cs.iastate.edu (Principal Investigator)
|
|
| Sponsor: |
Iowa State University
1138 Pearson
AMES, IA 50011 515/294-5225
|
|
| NSF Program(s): |
FOUNDATIONS
|
|
| Field Application(s): |
0000099 Other Applications NEC
|
|
| Program Reference Code(s): |
OTHR, 1616, 0000
|
|
| Program Element Code(s): |
1268
|
ABSTRACT
This Focused Research Group 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 have separately and jointly received large amounts of attention, and which come together in many of the examples and problems described in this proposal. Issues to be studied during the project 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. Activities of the group will include workshops, summer schools for graduate students, and travel for collaboration.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
|
(Showing: 1 - 10 of 17)
(Showing: 1 - 17 of 17)
|
Show All |
Aaron Sterling. "A Limit to the Power of Multiple Nucleation in Self-Assembly," Proceedings of the 22nd International Symposium on Distributed Computing, 2008, p. 451.
Jack H. Lutz. "A Divergence Formula for Randomness and Dimension," Mathematical Theory and Computational Practice: Proceedings of the Fifth Conference on Computability in Europe, 2009, p. 342.
Jack H. Lutz and Elvira Mayordomo. "Dimensions of points in self-similar fractals," SIAM Journal on Computing, v.38, 2008, p. 1080.
Jack H. Lutz and Elvira Mayordomo. "Dimensions of points in self-similar fractals," Proceedings of the Fourteenth Annual International Computing and Combinatorics Conference, 2008, p. 215.
Jack H. Lutz and Klaus Weihrauch. "Connectivity properties of dimension level sets," Proceedings of the Fourth International Conference on Computability and Complexity in Analysis, 2008, p. 295.
Jack H. Lutz and Klaus Weihrauch. "Connectivity properties of dimension level sets," Mathematical Logic Quarterly, v.54, 2008, p. 483.
James I. Lathrop, Jack H. Lutz, and Scott M. Summers. "Strict self-assembly of discrete Sierpinski triangles," Theoretical Computer Science, v.410, 2009, p. 384.
James I. Lathrop, Jack H. Lutz, and Scott M. Summers. "Strict self-assembly of discrete Sierpinski triangles," Computation and Logic in the Real World: Proceedings of the Third Conference on Computability in Europe, 2008, p. 455.
James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers. "Computability and complexity in self-assembly," Logic and Theory of Algorithms: Proceedings of the Fourth Conference on Computability in Europe, 2008, p. 349.
Matthew J. Patitz. "Simulation of Self-Assembly in the Abstract Tile Assembly Model with ISU TAS," Proceedings of the 6th Annual Conference of the Foundations of Nanoscience: Self-Assembled Architectures and Devices, 2009, p. 209.
Matthew J. Patitz and Scott M. Summers. "Self-assembly of discrete self-similar fractals," Proceedings of the Fourteenth International Meeting on DNA Computing, 2008, p. 156.
Matthew J. Patitz and Scott M. Summers. "Self-assembly of decidable sets," Proceedings of the Seventh International Conference on Unconventional Computation, 2008, p. 206.
Satyadev Nandakumar. "A Characterization of Constructive Dimension," Mathematical Logic Quarterly, v.55, 2009, p. 271.
Satyadev Nandakumar. "A characterization of constructive dimension," Proceedings of the Fourth International Conference on Computability and Complexity in Analysis, 2008, p. 323.
Satyadev Nandakumar. "An effective ergodic theorem and some applications," Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, p. 39.
Xiaoyang Gu and Jack H. Lutz. "Effective dimensions and relative frequencies," Logic and Theory of Algorithms: Proceedings of the Fourth Conference on Computability in Europe, 2008, p. 231.
Xiaoyang Gu and Jack H. Lutz. "Dimension Characterizations of Complexity Classes," Computational Complexity, v.17, 2008, p. 459.
|
(Showing: 1 - 10 of 17) (Showing: 1 - 17 of 17) |
Show All |
Please report errors in award information by writing to: awardsearch@nsf.gov.
|
|
|
