ANNOUNCEMENT AND CALL FOR PAPERS

WORKSHOP ON TYPICAL CASE COMPLEXITY AND PHASE TRANSITIONS

Affiliated with the IEEE Symposium on Logic in Computer Science, LICS 2003

June 21, 2003, Ottawa, Canada

WEB ADDRESS

www.scs.carleton.ca/∼kranakis/LICS-03.html

INVITED SPEAKERS

(confirmed)

Jennifer Chayes (Seattle) Nadia Creignou (Marseille) Paul Beame (Seattle) John Franco (Cincinnati)

ADDRESS FOR SUBMISSION

Short abstracts of at most five pages in postscript or pdf to:

kirousis@ceid.upatras.gr or kranakis@scs.carleton.ca

IMPORTANT DATES Typical-case complexity refers to algorithmic complexity that holds with high probability for a class of random instances of a problem. Usually, the class of instances considered is parameterized by a “control parameter.” It has been observed that for many computationally interesting problems, their typical-case complexity undergoes an abrupt change (phase transition) about a critical value of the control parameter. At the same critical region, other phenomena of combinatorial interest are often observed. Papers reporting on experimental and theoretical research in this area are solicited, especially if they are the outcome of crossfertilization between computer simulation results and mathematical advances in discrete mathematics, probability theory or theoretical computer science. Of particular interest are threshold phenomena in which logic comes into play and connections to Proof Complexity, Satisfiability, and Statistical Physics.

Program Committee: J. Chayes (Seattle, jchayes@microsoft.com) N. Creignou (Marseille, creignou@lim.univ-mrs.fr) L. Kirousis (Patras, kirousis@ceid.upatras.gr) E. Kranakis (Ottawa, kranakis@scs.carleton.ca) D. Krizanc (Middletown, dkrizanc@wesleyan.edu)

Organizers: L. Kirousis and E. Kranakis

Submission:  May 05, 2003 Notification:  May 12, 2003 Camera-ready abstracts: May 26, 2003