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


Please select your role
to obtain appropriate quick-links.
As a LIPIcs/OASIcs author, you will be invited by e-mail to register at the Dagstuhl Submission Server. The server will guide you through the publication workflow. Preliminary information can be found here:
Quick Links

Dagstuhl Seminar 06111

Complexity of Boolean Functions

( Mar 12 – Mar 17, 2006 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/06111
Organizers
Contact
Publications
Impacts
Summary
Show 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.

Participants
Show Participants
  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Alexander E. Andreev (LSI Logic Corp. - Milpitas, US)
  • Jan Arpe (Universität Lübeck, DE)
  • Frank Balbach (Universität Lübeck, DE)
  • Markus Bläser (Universität des Saarlandes, DE) [dblp]
  • Beate Bollig (TU Dortmund, DE) [dblp]
  • Jehoshua (Shuki) Bruck (CalTech - Pasadena, US)
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • Claude Carlet (University of Paris VIII, FR)
  • Carsten Damm (Universität Göttingen, DE)
  • Ronald de Wolf (CWI - Amsterdam, NL) [dblp]
  • Scott Diehl (University of Wisconsin - Madison, US)
  • Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
  • Eldar Fischer (Technion - Haifa, IL)
  • Lance Fortnow (University of Chicago, US) [dblp]
  • Anna Gál (University of Texas - Austin, US) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Frederic Green (Clark University - Worcester, US) [dblp]
  • Lisa Hellerstein (Polytechnic Institute of NYU - Brooklyn, US) [dblp]
  • Thomas Hofmeister (TU Dortmund, DE)
  • Kazuo Iwama (Kyoto University, JP) [dblp]
  • Andreas Jakoby (Universität Frankfurt, 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]
  • Matthias Krause (Universität Mannheim, DE) [dblp]
  • Miroslaw Kutylowski (Wroclaw University of Technology, PL)
  • Troy Lee (CWI - Amsterdam, NL) [dblp]
  • Maciej Liskiewicz (Universität Lübeck, DE)
  • 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]
  • Jakob Nordström (KTH Royal Institute of Technology, SE) [dblp]
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Ramamohan Paturi (University of California - San Diego, US) [dblp]
  • Konstantin Pervyshev (Steklov Institute - St. Petersburg, RU)
  • Pavel Pudlák (Czech Academy of Sciences, CZ) [dblp]
  • Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
  • Martin Sauerhoff (TU Dortmund, DE)
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Jiri Sgall (Czech Academy of Sciences - Prague, CZ) [dblp]
  • Ronen Shaltiel (University of Haifa, IL) [dblp]
  • Igor Shparlinski (Macquarie University - Sydney, AU) [dblp]
  • Detlef Sieling (TU Dortmund, DE)
  • Hans Ulrich Simon (Ruhr-Universität Bochum, DE) [dblp]
  • Till Tantau (Universität Lübeck, DE) [dblp]
  • Pascal Tesson (Laval University - Quebec, CA)
  • Thomas Thierauf (Hochschule Aalen, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Christopher Umans (CalTech - Pasadena, US) [dblp]
  • Dieter van Melkebeek (University of Wisconsin - Madison, US) [dblp]
  • Emanuele Viola (Harvard University - Cambridge, US) [dblp]
  • Stephan Waack (Universität Göttingen, DE)
  • Ingo Wegener (TU Dortmund, DE)
  • Philipp Woelfel (University of Toronto, CA) [dblp]
  • Thomas Zeugmann (Hokkaido Univ. - Sapporo, JP)
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 04141: Complexity of Boolean Functions (2004-03-28 - 2004-04-02) (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)
Seminar 06111
© 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH
ImprintContactAccessibilityPrivacy