Dagstuhl Seminar 04141
Complexity of Boolean Functions
( Mar 28 – Apr 02, 2004 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/04141
Organizers
- 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)
Contact
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).
- Alexander E. Andreev (Moscow State University, RU)
- Frederik Armknecht (Universität Mannheim, DE) [dblp]
- Beate Bollig (Universität Frankfurt, DE) [dblp]
- Jehoshua (Shuki) Bruck (CalTech - Pasadena, US)
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Ronald de Wolf (CWI - Amsterdam, NL) [dblp]
- Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
- William Hesse (Clarkson University - Potsdam, US)
- Thomas Hofmeister (TU Dortmund, DE)
- Kazuo Iwama (Kyoto University, JP) [dblp]
- Andreas Jakoby (Universität Lübeck, DE)
- Stasys Jukna (Universität Frankfurt, DE) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Eike Kiltz (CWI - Amsterdam, NL) [dblp]
- Hartmut Klauck (Universität Frankfurt, DE) [dblp]
- Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
- Daniel Král' (Charles University - Prague, CZ) [dblp]
- Matthias Krause (Universität Mannheim, DE) [dblp]
- Oded Lachish (University of Haifa, IL)
- Troy Lee (CWI - Amsterdam, NL) [dblp]
- Stefan Lucks (Universität Mannheim, DE) [dblp]
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- David A. Mix Barrington (University of Massachusetts - Amherst, US) [dblp]
- Ilan Newman (University of Haifa, IL) [dblp]
- Ramamohan Paturi (University of California - San Diego, US) [dblp]
- Pavel Pudlák (Czech Academy of Sciences, CZ) [dblp]
- Omer Reingold (Weizmann Institute - Rehovot, IL) [dblp]
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- Martin Sauerhoff (TU Dortmund, DE)
- Georg Schnitger (Universität Frankfurt, DE)
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Jiri Sgall (Czech Academy of Sciences - Prague, CZ) [dblp]
- Detlef Sieling (TU Dortmund, DE)
- Hans Ulrich Simon (Ruhr-Universität Bochum, DE) [dblp]
- Robert Spalek (CWI - Amsterdam, NL)
- Pascal Tesson (McGill University - Montreal, CA)
- 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]
- Andrew C. Yao (Princeton University, US)
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 02121: Complexity of Boolean Functions (2002-03-17 - 2002-03-22) (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)
- Dagstuhl Seminar 25111: Computational Complexity of Discrete Problems (2025-03-09 - 2025-03-14) (Details)
