Center for Discrete Mathematics &
Theoretical Computer Science

Complexity and Inference
June 2 - 6, 2003

DIMACS Center
Rutgers University
Piscataway, NJ

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.

Because we have recently secured funding from the ARO and the NSA, we have extended our deadlines!
· March 1, 2003
Extended Abstracts due
· April 1, 2003
Notification of decisions
· Mark Hansen
UCLA
· Paul Vitanyi
CWI & University of Amsterdam
· Bin Yu
UC Berkeley
· Dimacs
The Center for Discrete Mathematics & Theoretical Computer Science
· Flyer
PDF Format, Please Post!
· Format of the Program
· Funding Sources