http://www.dagstuhl.de/99441

31. Oktober – 05. November 1999, Dagstuhl Seminar 99441

Complexity of Boolean Functions

Organisatoren

D. M. Barrington (Amherst), R. Reischuk (Lübeck), I. Wegener (Dortmund)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl's Impact: Dokumente verfügbar
Dagstuhl-Seminar-Report 257

The complexity of Boolean functions is one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify Boolean functions according to various complexity measures, such as the minimal size of Boolean circuits needed to compute specific functions.

Upper bounds on the size have been investigated, which result from clever methods and circuit designs to compute the functions, as well as lower bounds, which are established by showing that a function cannot be computed correctly given certain constraints. In spite of enormous efforts, there still seems to be a long way to go before successfully establishing large lower bounds in the most general case, of unrestricted circuits over complete bases.

To approach this goal a variety of restricted models have been considered, a number of elegant techniques have been developed for these models, and deep results have been obtained. Surprisingly, also at first glance very different questions like the communication complexity when computing discrete functions distributively, have been shown to be in quite tight relation to the complexity of Boolean functions.

The following is a list of main topics to be discussed:

  • lower bounds, circuits with unbounded fanin and depth restrictions
  • binary decision diagrams (BDD), algebraic models
  • communication complexity, delay and average-case complexity, reliability
  • upper bounds, relations to other computational models -- in particular neural nets and quantum computing
  • learning complexity, proof complexity

Dagstuhl Seminar Series

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.