TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 99441

Complexity of Boolean Functions

( Oct 31 – Nov 05, 1999 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/99441

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




Motivation

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

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

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 02121: Complexity of Boolean Functions (2002-03-17 - 2002-03-22) (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)
  • Dagstuhl Seminar 25111: Computational Complexity of Discrete Problems (2025-03-09 - 2025-03-14) (Details)