Computational Complexity of Discrete Problems

Organizers

Martin Grohe (HU Berlin, DE)
Michal Koucký (Academy of Sciences - Prague, CZ)
Rüdiger Reischuk (Universität Lübeck, DE)
Dieter van Melkebeek (University of Wisconsin - Madison, US)

Preliminary Motivation Text

This seminar is a continuation of a seminar series that has been held regularly at Dagstuhl since the foundation of IFBI. It was first called "Complexity of Boolean Functions", but we changed the name last time to "Computational Complexity of Discrete Functions" to reflect the broadening in focus from nonuniform models to also include uniform ones.

Seminar Series

08381: "Computational Complexity of Discrete Problems " (2008)
06111: "Complexity of Boolean Functions" (2006)
04141: "Complexity of Boolean Functions" (2004)
02121: "Complexity of Boolean Functions" (2002)
99411: "Temporal Logics for Distributed Systems - Paradigms and Algorithms" (1999)
9711: "Complexity of Boolean Functions" (1997)
9235: "Complexity and Realization of Boolean Functions" (1992)

Classification

Data structures / algorithms / complexity

Keywords

Computational complexity
Discrete problems
Turing machines
Circuits

Publications

Books from the participants of the current Seminar

Book exhibition in the library, 1st floor

(during the seminar week)

Each Dagstuhl Seminar has the possibility to publish a volume of "Dagstuhl Seminar Proceedings" online. Details will be discussed during the seminar.

Background information on

Dagstuhl Seminar Proceedings

Follow-Up Publications

Please inform us, when a further publication results from your seminar. These Follow-Up publications are listed separately and are presented on a special shelf on the ground floor of the library.