https://www.dagstuhl.de/04141

### March 28 – April 2 , 2004, Dagstuhl Seminar 04141

# Complexity of Boolean Functions

## 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)

## For support, please contact

## Documents

List of Participants

Dagstuhl's Impact: Documents available

## Background

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.

## Summary

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

- 21121: "Computational Complexity of Discrete Problems" (2021)
- 19121: "Computational Complexity of Discrete Problems" (2019)
- 17121: "Computational Complexity of Discrete Problems" (2017)
- 14121: "Computational Complexity of Discrete Problems" (2014)
- 11121: "Computational Complexity of Discrete Problems" (2011)
- 08381: "Computational Complexity of Discrete Problems" (2008)
- 06111: "Complexity of Boolean Functions " (2006)
- 02121: "Complexity of Boolean Functions" (2002)
- 99441: "Complexity of Boolean Functions" (1999)
- 9711: "Complexity of Boolean Functions" (1997)
- 9235: "Complexity and Realization of Boolean Functions" (1992)