Special Issue of
Discrete Applied Mathemetics
dedicated to the worksop on
TYPICAL CASE COMPLEXITY AND PHASE TRANSITIONS.

• Research Topic: 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.
• Scope: Papers reporting on original experimental and theoretical research in this area are solicited, especially if they are the outcome of cross-fertilization 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.
• Guest Editors: Lefteris M. Kirousis and Evangelos Kranakis
• Submission Guidelines:
  • Submit to either of
    Lefteris M. Kirousis (kirousis@ceid.upatras.gr)
    Evangelos Kranakis (kranakis@scs.carleton.ca)
  • Format of submission: ps or pdf.
  • Deadline for submission: Dec 01, 2003.
  All papers will be refereed according to the standards of DAM.