Dagstuhl-Seminar 06111
Complexity of Boolean Functions
( 12. Mar – 17. Mar, 2006 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/06111
Organisatoren
- 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)
Kontakt
Impacts
- Incremental branching programs : article : S. 159-184 (based on Dagstuhl Seminars 04141, 04421, 06111, 07411 - Gal, Anna; Koucky, Michal; MacKenzie, Pierre - Berlin : Springer, 2008 - (Theory of computing systems : 43. 2008, 2 : S. 159-184). DOI: 10.1007/s00224-007-9049-y.
- Tight Bounds for Blind Search on the Integers and the Reals : Article : pp. 711-728 - Dietzfelbinger, Martin; Rowe, Jonathan E.; Wegener, Ingo; Woelfel, Philipp - Cambridge : Cambridge University Press, 2010 - (Combinatorics, probability and computing : 19. 2010, 5/6 : pp. 711-768). DOI: 10.1017/S0963548309990599.
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.
- 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)
Verwandte Seminare
- 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)
