Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 02121

Complexity of Boolean Functions

( Mar 17 – Mar 22, 2002 )

Please use the following short url to reference this page:



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.

  • Mikhail Alekhnovitch (Institute of Advanced Study - Princeton, US)
  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Alexander E. Andreev (Moscow State University, RU)
  • Paul Beame (University of Washington - Seattle, US) [dblp]
  • Eli Ben-Sasson (Technion - Haifa, IL) [dblp]
  • Beate Bollig (Universität Frankfurt, DE) [dblp]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • Peter Damaschke (Chalmers UT - Göteborg, SE) [dblp]
  • Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
  • Jürgen Forster (Ruhr-Universität Bochum, DE)
  • Anna Gál (University of Texas - Austin, US) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Jovan Golic (Gemplus - Roma, IT)
  • Venkatesan Guruswami (University of Washington - Seattle, US) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Thomas Hofmeister (TU Dortmund, DE)
  • Andreas Jakoby (Universität Lübeck, DE)
  • Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Pawel Kerntopf (Warsaw University of Technology, PL)
  • Hartmut Klauck (Universität Frankfurt, DE) [dblp]
  • Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Matthias Krause (Universität Mannheim, DE) [dblp]
  • Klaus-Jörn Lange (Universität Tübingen, DE) [dblp]
  • Bruce Litow (James Cook University - Cairns, AU)
  • Stefan Lucks (Universität Mannheim, DE) [dblp]
  • Akira Maruoka (Tohoku University - Sendai, JP)
  • Wolfgang Merkle (Universität Heidelberg, DE) [dblp]
  • Peter Bro Miltersen (Aarhus University, DK) [dblp]
  • David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
  • Elizaveta Okol'nishnikova (Sobolev Institute of Mathematics - Novosibirsk, RU)
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Prabhakar Ragde (University of Waterloo, CA)
  • Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
  • Martin Sauerhoff (TU Dortmund, DE)
  • Petr Savicky (Academy of Science - Prague, CZ) [dblp]
  • Georg Schnitger (Universität Frankfurt, DE)
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Bodo Siebert (Universität Lübeck, DE)
  • Detlef Sieling (TU Dortmund, DE)
  • Hans Ulrich Simon (Ruhr-Universität Bochum, DE) [dblp]
  • Denis Therien (McGill University - Montreal, CA) [dblp]
  • Thomas Thierauf (FH Aalen, DE) [dblp]
  • Dieter van Melkebeek (University of Wisconsin - Madison, US) [dblp]
  • Stephan Waack (Universität Göttingen, DE)
  • Ingo Wegener (TU Dortmund, DE)
  • Philipp Woelfel (University of Toronto, CA) [dblp]
  • Stanislav Zak (Academy of Science - Prague, CZ)
  • Erik Zenner (Universität Mannheim, DE)
  • Thomas Zeugmann (Hokkaido Univ. - Sapporo, JP)

Related Seminars
  • Dagstuhl Seminar 9235: Complexity and Realization of Boolean Functions (1992-08-24 - 1992-08-28) (Details)
  • Dagstuhl Seminar 9711: Complexity of Boolean Functions (1997-03-10 - 1997-03-14) (Details)
  • Dagstuhl Seminar 99441: Complexity of Boolean Functions (1999-10-31 - 1999-11-05) (Details)
  • Dagstuhl Seminar 04141: Complexity of Boolean Functions (2004-03-28 - 2004-04-02) (Details)
  • Dagstuhl Seminar 06111: Complexity of Boolean Functions (2006-03-12 - 2006-03-17) (Details)
  • Dagstuhl Seminar 08381: Computational Complexity of Discrete Problems (2008-09-14 - 2008-09-19) (Details)
  • Dagstuhl Seminar 11121: Computational Complexity of Discrete Problems (2011-03-20 - 2011-03-25) (Details)
  • Dagstuhl Seminar 14121: Computational Complexity of Discrete Problems (2014-03-16 - 2014-03-21) (Details)
  • Dagstuhl Seminar 17121: Computational Complexity of Discrete Problems (2017-03-19 - 2017-03-24) (Details)
  • Dagstuhl Seminar 19121: Computational Complexity of Discrete Problems (2019-03-17 - 2019-03-22) (Details)
  • Dagstuhl Seminar 21121: Computational Complexity of Discrete Problems (2021-03-21 - 2021-03-26) (Details)
  • Dagstuhl Seminar 23111: Computational Complexity of Discrete Problems (2023-03-12 - 2023-03-17) (Details)