Background
The notion of algorithmic complexity was suggested independently by
Kolmogorov, Chaitin, and Solomonoff in the 1960's. Both Kolmogorov and
Chaitin introduced the concept as a way to formalize notions of
entropy and randomness, building on results from theoretical computer
science dealing with partial recursive functions. Independently,
Solomonoff defined algorithmic complexity in the pursuit of universal
priors for statistical inference. In recent years, Rissanen expanded
the applicability of these ideas, employing well-established concepts
from information theory to frame his principle of Minimum Description
Length (MDL) for statistical inference and model selection.
Each of these lines of research has developed methods for describing
data (through coding and compression, or by analogy with some formal
computing device); and each of these lines has employed some concept
of an efficient representation to guide statistical inference. In
this workshop, we will explore both the foundational aspects of
complexity-based inference as well as applications of these ideas to
challenging modeling problems. Participants will be drawn from the
fields of statistics, information and coding theory, machine learning,
and complexity theory. Application areas include biology, information
technologies, physics and psychology.
The following specific topics will be covered by the workshop:
| · |
Kolmogorov complexity and inference
|
· |
MDL (MML)
theory and applications
|
| · |
Lossy compression and complexity theory
|
· |
Complexity and Bayesian methods
|
| · |
Individual sequence/on-line
prediction and predictive complexity
|
· |
Compression methods for clustering
|
| · |
Machine learning and
computational complexity
|
· |
Complexity and cognitive science
|
| · |
Applications
|
|
|
Confirmed Invited Participants Jont Allen, Andrew Barron,
William Bialek,
Nick Chater, Philip Dawid, Alexandros Eleftheriadis,
Peter Gacs, Andrew Gelman, Peter Grunwald, Peter van der Helm,
Robert Kass, Diane Lambert, Ron Meir,
Jorma Rissanen, Ray Solomonoff, Marcelo Weinberger, Vladimir Vovk
Contributed Presentations While leading researchers in each of
these areas are being invited to participate in the workshop,
submissions of contributed papers of original works in these areas
are now being solicited. Papers will be reviewed on the basis of an
extended abstract (not exceeding 3 pages) to allow for a reasonable
review. The deadline for submission is March 1, 2003, with
notification of decisions by April 1, 2003. Authors are
required to submit electronic versions of their abstracts in PDF form
to complexity@research.bell-labs.com
.
Financial Support: We are happy to report that both the ARO and
the NSA will provide financial support for this workshop.
Therefore, we can offer partial funding to
people wishing to attend. Students, recent Ph.D.'s,
women and minorities are particularly encouraged to apply. To apply
for funding, send a letter explaining your interest in the workshop
together with a vita or bibliography and a budget for travel/living
expenses. If you are a student, also solicit a letter from a faculty
adviser.