### DIMACS Workshop on Complexity and Inference

#### June 2 - 5, 2003

DIMACS Center, Rutgers University, Piscataway, NJ

**Organizers:**
** Mark Hansen**, Bell Laboratories, cocteau@stat.ucla.edu
** Paul Vitanyi**, CWI and the University of Amsterdam, Paul.Vitanyi@cwi.nl
** Bin Yu**, UC Berkeley, binyu@stat.berkeley.edu

Presented under the auspices of the
Special Focus on Computational Information Theory and Coding.

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

**Financial Support:** A limited amount of funding is available for
partial support of people wishing to attend. Students, recent Ph.D.'s,
women and minorities are particularly encouraged to apply. To apply
for funding, send a letter to complexity@research.bell-labs.com 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.

Next: Call for Participation

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on May 7, 2003.