28. März – 02. April 2004, Dagstuhl-Seminar 04141

Complexity of Boolean Functions


Johan Hastad (KTH Royal Institute of Technology, SE)
Matthias Krause (Universität Mannheim, DE)
Pavel Pudlák (Czech Academy of Sciences, CZ)
Ingo Wegener (TU Dortmund, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl's Impact: Dokumente verfügbar


The determination of the complexity of Boolean functions with respect to various hardware models, like Boolean circuits, branching programs or constant layer feedforward neural networks, is one of the central and classical topics in the theory of computation. It implies the search for efficient implementations for hardware relevant functions as well as proofs of lower bounds which are established by showing that a given function cannot be computed correctly given certain constraints. In this respect a lot of interesting and surprising results have been obtained which in many cases are based on the development of elegant and very nontrivial mathematical techniques. Methods originally intended to better analyze the complexity of Boolean functions have interesting implications in other areas like hardware verification, computational intelligence and cryptography.

The aim of this seminar was to collect the leading experts of Booelan complexity theory, and to present the latest results in this area. Besides this, a main item in the discussion were new challenges like the analysis of fault tolerant circuits and circuits with feedback or the question if classical complexity theoretic results do hold in the quantum computing setting. A number of successfull applications of Boolean complexity methods in other more applied fields like hardware design and verification, algorithmic learning, quantum computing and cryptanalysis of block- and stream ciphers were presented.


The talks of the seminar covered a wide spectrum of recently studied questions of Theoretical Computer Science related to the complexity of Boolean functions in nonuniform models. Besides talks on new results for the classical problems in circuit complexity theory (Tesson, Lachish, Bro Miltersen, Tesson, Therien, Kiltz, Jukna) we had contribution on new challenges for Boolean complexity theory like analyzing circuits with feedback (Bruck) or fault tolerant circuits (Newman). Other talks were related to efficient hardware implementations for Boolean functions of practical interest like the integer multiplication (Wölfel), memory functions (Andreev), cryptographic functions (Kiltz) or perfect matching (Thierauf). Also areas of uniform complexity theory like Kolmogorov complexity theory (Lee, Buhman, Koucky) and structural complexity theory (Kabanets, Hesse) were present. One of the deepest results in complexity theory is the PCP-theorem, characterizing the power probabilistic proof checking. There was a very interesting talk (Reingold) on the search for an easier, more combinatorial and circuit-based proof of the PCP-theorem.

A more applied field which is closely connected to Boolean complexity theory is hardware verification. In this context there were presented interesting contributions on the computational power and algorithmic properties of binary decision diagrams (Wölfel, Sieling, Waack) and on the tractability of SAT problems (van Melkebeek, Iwama, Hofmeister). A classical and in many cases very successful approach to the analysis of restricted hardware models is to describe them in terms of appropriate communication games. We heared interesting talks on characterizing regular languages (Tesson) and contextfree languages and the power of deterministic and randomized pushdown automata (Schnitger) in terms of communication complexity.

A comparatively large number of talks were devoted to a further estimation of the power of quantum models of computation (de Wolf, Klauck, Yao, Jacobi, Spalek). A recent focus in this context is to try to answer the question to which extend basic results of classical complexity theory do hold in a quantum setting.

Last but not least we heared about new results in two traditional application fields for Boolean complexity theory, algorithmic learning theory (Simon, Reischuk), and cryptography, especially cryptanalysis of block- and stream ciphers (Armknecht, Lucks).

Dagstuhl-Seminar Series


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.