LICS'03
Workshop on
TYPICAL CASE COMPLEXITY AND PHASE TRANSITIONS
June 21, 2003, Ottawa, Canada
(download poster in
ps ,
and in
text .)
Supported by:
CRM ,
MITACS, and
M.P.L.A.
Special Issue of Discrete Applied Mathematics
Organizers:
Lefteris M. Kirousis (UoPatras),
Evangelos Kranakis (CarletonU)
DOWNLOAD PICTURES OF SOME WORKSHOP PARTICIPANTS
SCIENTIFIC PROGRAM
Location: SITE, Room F0126
INVITED SPEAKERS
09:00 - 10:30
John Franco (UoCincinnati)
Probabilistic Analysis of Satisfiability
Algorithms and Structural Properties
(abstract)
(Download Tutorial, 31 MB)
10:30 - 11:00 Coffee Break
11:00 - 11:45
Andreas Goerdt (TU Chemmitz)
Efficient recognition of random unsatisfiable k-SAT instances
(abstract)
11:45 - 12:30
Paul Beame (UoWashington)
Proof complexity and complete algorithms for NP-hard search problems
(abstract)
12:30 - 13:45 Lunch
13:45 - 14:30
Albert Atserias (U Politcnica de Catalunya)
On sufficient conditions for unsatisfiability
(abstract)
CONTRIBUTED PAPERS
14:30 - 15:00
An Empirical Study of MAX-2-SAT Phase Transitions
(paper)
Haiou Shen and Hantao Zhang (University of Iowa)
15:00 - 15:30
Selecting Complementary Pairs of Literals
(paper)
Alexis C. Kaporis, Lefteris M. Kirouis and Efthimikos G. Lalas
(University of Patras)
15:30 - 16:00 Coffee Break
16:00 - 16:30
Recognizing More Random Unsatisfiable 3-SAT Instances Efficiently
(paper)
Andreas Goerdt and Andre Lanka (Technische Universitaet Chemnitz)
16:30 - 17:00
An Efficient Local Search Method for Random 3-Satisfiability
(paper)
Sakari Seitz and Pekka Orponnen (Helsinki University of Technology)
17:00 - 17:30
Resolution Complexity of Random Constraint Satisfaction
Problems: Another Half of the Story
(paper)
Yong Gao and Joseph Culberson (University of Alberta)
Publication:
A special issue of Discrete Applied Mathemetics will be
dedicated to the worksop. Details will be announced at a
later time.
RESEARCH SUMMARY AND SCOPE
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.
SUBMISSIONS
Submit to: kirousis@ceid.upatras.gr or kranakis@scs.carleton.ca
Format: postscript or pdf
Deadline for paper submission: Monday, May 05
Notification of acceptance: Monday, May 12
Final copy due (to be distributed at the conference and linked in the
workshop page): Monday, May 26.
PROGRAM COMMITTEE
Jennifer Chayes (Seattle, jchayes@microsoft.com)
Nadia Creignou (Marseille, Nadia.Creignou@lidil.univ-mrs.fr)
Lefteris M. Kirousis (Patras, kirousis@ceid.upatras.gr)
Evangelos Kranakis (Ottawa, kranakis@scs.carleton.ca)
Danny Krizanc (Middletown, dkrizanc@wesleyan.edu)
LOCAL INFORMATION
Accomodation:
Hotels and Workshop Location
Registration
Talks to be held at UoOttawa:
SITE