TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 03141

The Propositional Satisfiability Problem -- Algorithms and Lower Bounds

( 30. Mar – 04. Apr, 2003 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/03141

Organisatoren



Summary

The propositional satisfiability problem is the basic problem for which efficient algorithms in the classical sense do not exist. However, theoretical and applied computer scientists are clearly interested in this problem. On the applied side the satisfiability problem is seen as a aa paradigmatic combinatorial search problem. It is a special type of constraint satisfaction problem. And constraint satisfaction problems allow for a natural modeling of real life search problems. On the theoretical side two complementary aspects of the satisfiability problem are the focus of recent research: First, developing algorithms with provable performance guarantees, and second, proving lower bounds of any kind.Recently scientific progress has been made in each of the aforementioned areas.

Due to the diversity of the techniques employed the corresponding scientific groups tend to be in part disjoint. It is the obvious purpose of the seminar to bring these groups together.

The seminar fulfilled its purpose in any respect. Most of the about 20 talks dealt directly with algorithmic aspects of the problem, most interestingly some experimental and theoretical analyses of local search algorithms were presented. Three talks from the applied area are also worth mentioning. In two of them satisfability instances arising from cryptographic applications were presented and one dealt with satisfiability instances arising form the area of configuration (of cars). These talks were particularly interesting to algorithm designers because they made them familiar with complex instances from real life. Experience will show, if this has served as a starting point of a fruitful collaboration.

The understanding of random propositional formulas in conjunctive normalform is still one of the major open problem areas. The relavant ''satisfiability threshold conjecture '' is based on an experimentally claearly visible phenomenon, but is is still only to a small part proven by now. The conjecture asserts that formulas with approximately 4.2?n many randomly chosen 3-clauses become suddenly unsatisfiable.

A couple of open problems where discussed by the participants during an open problem session. These are contained in the proceedings.


Teilnehmer
  • Michael Alekhnovich (MIT - Cambridge, US)
  • Albert Atserias (UPC - Barcelona, ES) [dblp]
  • Stefan Dantchev (University of Leicester, GB) [dblp]
  • Evgeny Dantsin (Roosevelt University - Chicago, US)
  • Hervé Daude (University of Marseille, FR)
  • Juan Luis Esteban (UPC - Barcelona, ES)
  • John Franco (University of Cincinnati, US) [dblp]
  • Nicola Galesi (Sapienza University of Rome, IT) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Edward A. Hirsch (Steklov Institute - St. Petersburg, RU) [dblp]
  • Thomas Hofmeister (TU Dortmund, DE)
  • Kazuo Iwama (Kyoto University, JP) [dblp]
  • Emil Jerabek (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Jan Johannsen (LMU München, DE) [dblp]
  • Alexis Kaporis (CTI & University of Patras, GR)
  • Lefteris M. Kirousis (CTI & University of Patras, GR) [dblp]
  • Johannes Köbler (HU Berlin, DE) [dblp]
  • Matthias Krause (Universität Mannheim, DE) [dblp]
  • Wolfgang Küchlin (Universität Tübingen, DE) [dblp]
  • Oliver Kullmann (Swansea University, GB) [dblp]
  • Wolfgang Lindner (Universität Ulm, DE)
  • Alexis Maciel (Clarkson University - Potsdam, US)
  • Jochen Messner (Universität Ulm, DE) [dblp]
  • Remi Monasson (CNRS - Paris, FR) [dblp]
  • Martin Mundhenk (Universität Jena, DE) [dblp]
  • Ramamohan Paturi (University of California - San Diego, US) [dblp]
  • Stefan Porschen (Universität Köln, DE)
  • Pavel Pudlák (Czech Academy of Sciences, CZ) [dblp]
  • Soren Riis (Queen Mary University of London, GB)
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Rainer Schuler (Universität Ulm, DE)
  • Carsten Sinz (Universität Tübingen, DE) [dblp]
  • Ewald Speckenmeyer (Universität Köln, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Iannis Tourlakis (Princeton University, US)
  • Hans Van Maaren (TU Delft, NL)
  • Anastasios Viglas (University of Toronto, CA)
  • Toby Walsh (Univ. of New South Wales - Sydney, AU) [dblp]
  • Osamu Watanabe (Tokyo Institute of Technology, JP)
  • Huaitao Zhang (Queen Mary University of London, GB)