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.


Topics
· 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
Center for Discrete Mathematics &
Theoretical Computer Science

Complexity and Inference
June 2-5, 2003

DIMACS Center
Rutgers University
Piscataway, NJ

Organizers:
Mark Hansen, Paul Vitanyi, Bin Yu

Preliminary Program:
[ Schedule | Contributed Abstracts ]

· DIMACS Workshop Announcement
· Information on accommodation
· Travel information

Confirmed Participants
Jont Allen, Andrew Barron, William Bialek, Nick Chater, Philip Dawid, Alexandros Eleftheriadis, Lance Fortnow, Dean Foster, Peter Gacs, Andrew Gelman, Peter Grunwald, Peter van der Helm, Ron Meir, Jorma Rissanen, Serap Savari, Ray Solomonoff, Florin Vaida, Vladimir Vovk, Marcelo Weinberger, Abraham Wyner