Volume on Computational Complexity and Statistical Physics

In September 2001, we held a Workshop on Computational Complexity and Statistical Physics in Santa Fe, New Mexico. In conjunction with this meeting and with the June 2002 Workshop on Phase Transitions and Algorithmic Complexity at UCLA, we are soliciting contributions to a peer-reviewed, edited volume.

The volume is intended for publication by Oxford University Press as part of the "Santa Fe Institute Studies in the Sciences of Complexity" series. This book, like the workshops, will focus on the relationship between methods from statistical physics and algorithmic complexity, particularly as relating to the study of phase transitions in combinatorial problems.

While many of the contributions to this volume are likely to be from participants at one of the two workshops, we encourage you to consider submitting a paper even if you are not in this category. The book is intended is provide an overview of the emerging field, rather than simply serving the role of workshop proceedings.

Papers should be kept at a level where they may be appreciated by an interdisciplinary audience. The main target communities are computer scientists, physicists and mathematicians. Review papers giving a broad perspective are particularly welcome, though we plan to have articles presenting new results as well. Manuscripts should be limited to a maximum of 20 pages, and will be edited to provide for thematic cohesion. Specific topics falling within the scope of the book might include:

• Complexity theory
• Combinatorial optimization
• Disordered systems
• Replica symmetry
• Random graphs
• Sharp thresholds
• Satisfiability
• Backbones
• Heuristic methods and experimental results
• Rapidly mixing Markov chains
• Proof complexity

Submit title/abstract: Submit manuscript: Manuscript reviews received: Acceptance decisions sent: Submit final version of manuscript:

June 24, 2002 October 1, 2002 January 6, 2003 January 10, 2003 February 10, 2003

Submissions should be e-mailed to: phasetrans@santafe.edu. If you have any questions, please do not hesitate to contact any of the editors listed below. Detailed guidelines on format, etc., will be sent out in July/August.

We look forward to hearing from you.

With best wishes,

Allon Percus, percus@lanl.gov
Gabriel Istrate, istrate@lanl.gov
Cris Moore, moore@santafe.edu

Last modified: 2 June 2002