Many talks of the seminar dealt with new techniques for analyzing the computational power of basic models to compute Boolean functions. In particular, branching programs were discussed most extensively. At the first day we had a keynote talk in the morning and an evening discussion on time-space tradeoff results on the level of branching programs (Beame). Several talks on refined lower bound methods for non deterministic and randomized free BDDs (Okol'nishnikova, Zk, Sauerhoff, Wölfel) and the approximability of Boolean functions by OBDDs (Wegener) followed. Other important topics were new results concerning distributed computing of Boolean functions (Jakoby) and communication complexity (Forster, Thérien, and several BDD talks). One highlight here was the presentation of and the discussions on Forsters technique to prove almost optimal lower bounds on the unbounded error probabilistic communication complexity of particular Boolean functions (Forster, Simon). Further talks considered the comparison of classical models and related quantum models for computing Boolean functions (Sieling, Klauck, van Melkebeek, Fuhrman, Kerntopf). In addition, besides presenting his own results, Klauck discussed Razborov's very recent solution to a long open problem on deterministic versus probabilistic quantum communication complexity.

Other talks of the seminar dealt with methods for better determining the complexity of hardware relevant Boolean functions (like integer multiplication) with respect to models used as data structures in hardware verification (Bollig, Wolfed), the computational power of decision lists (Krause), and new results on the power of span programs (G´ al). Efficient algorithms was another main topic, especially concerning restricted types of circuits and branching programs as data structures for manipulating, minimizing and learning Boolean functions. Here we had several interesting talks about latest progress in SAT algorithms (Hofmeister, Goerdt, Alekhnovich), new developments in proof complexity (Ben-Sasson, Alekhnovich), new positive and negative results on the learnability of DNFs and AND-decision lists (Maruoka, Krause), and fixed-parameter tractability (Ragde). Further talks were concerned with relations between Boolean complexity topics and uniform complexity theory, especially with the complexity of derandomizing probabilistic algorithms (Allender, Kabanets), and the closely connected topics of characterizing logspace-classes (Thierauf) and the uniform complexity of reachability problems (Koucky, Barrington). Several talks stressed, at least implicitely, cryptographic implications of structural and complexity-theoretic results on Boolean functions, especially from the viewpoint of design and security criterions for cryptographic primitives like pseudorandom functions and permutations and S-Box functions (Golic, Lucks). The contributions of this seminar showed that several new trends in Boolean complexity have gained increased consideration, in particular proof complexity and computing with quantum bits. We have discussed in detail how far our current proof methods have brought us to precisely determine the computational complexity of Boolean functions for general computational models.

The seminar had a number of younger European researchers who for the first time had a chance to take part in such a detailed discussion on current research topics in Boolean complexity. About half of the presentations were given by participants from outside the European Union. The research on Boolean functions is conducted in a broad international exchange. We felt that this meeting at the IFBI was quite productive for all participants concerning their own future research.

Public Outreach

To determine 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. This includes the search for efficient implementations of hardware relevant functions, like address functions and arithmetic and logical operations. On the other hand, we strive for establishing lower bounds on the computational complexity showing that a certain function cannot be computed if a certain amount of resources is not available. In this respect, a lot of interesting and surprising results have been obtained, which in many cases are based on the development of elegant, highly nontrivial mathematical proof techniques. However, in spite of enormous efforts, there still seems to be quite a long way to go before getting tight characterizations of the complexity of important functions for general types of circuits and branching programs. Methods originally designed to analyze the complexity of Boolean functions turned out to 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 Boolean complexity theory and to present the latest results in this area. One main focus was to discuss successful applications of Boolean complexity methods in other more applied fields like hardware design and verification, algorithmic learning, neural computing, proof complexity theory, quantum computing, design of cryptographic primitives, and cryptoanalysis of block and stream ciphers.