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 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.
PROGRAM COMMITTEE
J. Chayes (Seattle, [email protected])
N. Creignou (Marseille, [email protected])
L. Kirousis (Patras, [email protected])
E. Kranakis (Ottawa, [email protected])
D. Krizanc (Middletown, [email protected])