http://www.dagstuhl.de/06111

### March 12 – 17 , 2006, Dagstuhl Seminar 06111

# Complexity of Boolean Functions

## Organizers

Matthias Krause (Universität Mannheim, DE)

Pavel Pudlák (Czech Academy of Sciences, CZ)

Rüdiger Reischuk (Universität Lübeck, DE)

Dieter van Melkebeek (University of Wisconsin – Madison, US)

## For support, please contact

## Documents

Dagstuhl Seminar Proceedings

List of Participants

Dagstuhl's Impact: Documents available

## Summary

Estimating the computational complexity of discrete functions is one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean functions according to fundamental complexity measures like Boolean circuit size and depth. A variety of other nonuniform computational models with individual bit operations have been considered: bounded fan-in circuits, formulae, branching programs, binary decision diagrams (BDDs), span programs, etc. The analysis and relative power of these models remains a major challenge. For models of low expressive power, non-trivial efficient realizations of certain hardware-relevant functions have been found, but this question is still open in many cases. Several lower bound techniques for explicitly defined Boolean functions have been developed -- most of them are of combinatorial nature. Such negative results are not only of theoretical value, but would have constructive implications, for example in cryptography and derandomization.

Methods that were originally designed to analyze the expressive power of restricted circuit models have also yielded interesting applications in other areas, such as hardware design and verification, algorithmic learning, neural computing, and quantum computing. This leads to the problem as to what type of proof method might be developed and applied at all in this setting. For higher complexity classes, we now know that the existence of natural lower bound arguments would disprove widely believed hardness assumptions. Thus, novel approaches are needed to establish lower bounds for more expressive models in discrete computational complexity.

Nowadays, investigations on the computational complexity of discrete functions have diverged and specialized into many different branches such that it becomes hard to keep a close look at all approaches. Thus, it is important to bring together researchers from different subareas in a more relaxed atmosphere Dagstuhl provides (as compared to the situation at the major international conferences in this field like STACS, STOC, CC or FOCS) to foster interaction and exchange of new ideas that might be applied in other settings as well. On the one hand, we wanted to present some of the most recent results in the different subareas to a broader audience, in particular in currently fast developing areas like, for example, approximation, communication and proof complexity or quantum computing. Secondly, we wanted to give the opportunity to discuss extensions of different proof methods as well as their applications to other fields.

Understanding the complexity of Boolean functions is still one of the fundamental tasks in the theory of computation. At present, besides classical methods like substitution or degree arguments a bunch of combinatorial and algebraic techniques have been introduced to tackle this extremely difficult problem. These techniques have also found applications in other areas of computational complexity -- in some cases it worked also the other way around. There has been significant progress analysing the power of randomness and quantum bits or multiparty communication protocols that help to capture the complexity of Boolean functions. For tight estimations concerning the basic, most simple model -- Boolean circuits -- there still seems a long way to go.

## Dagstuhl Seminar Series

- 14121: "Computational Complexity of Discrete Problems" (2014)
- 11121: "Computational Complexity of Discrete Problems" (2011)
- 08381: "Computational Complexity of Discrete Problems" (2008)
- 04141: "Complexity of Boolean Functions" (2004)
- 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)