- 作者：Evangelos Kranakis ; Lefteris Kirousis
- 关键词：phase transition ; satisfiability ; Davis-Putnam algorithm ; probabilistic analysis ; differential equations
- 刊名：Electronic Notes in Discrete Mathematics
- 出版年：2003
- 出版时间：October 2003
- 年：2003
- 卷：16
- 期：Complete
- 页码：93
- 全文大小：22 K
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. The workshop focused on research that resulted from cross-fertilization between computer simulation results and mathematical advances in discrete mathematics, probability theory or theoretical computer science. Of particular interest were threshold phenomena in which logic comes into play or have connections with proof complexity, satisfiability, and statistical physics.
The editors would like to thank the invited speakers: Albert Atserias (Universitat Politècnica de Catalunya), Paul Beame (University of Washington), John Franco (University of Cincinnati), and Andreas Goerdt (Technische Universität Chemnitz) as well as the other members of the program committee: Jennifer Chayes (Microsoft), Nadia Creignou (Université d'Aix-Marseille II), and Danny Krizanc (Wesleyan University).
Evangelos Kranakis (Carleton University)
Lefteris Kirousis (University of Patras)