2006/01/01 by Matthias Krause, Dieter van Melkebeek, Krause, Matthias +5 · 1 citation
Computer Science · #Advanced Algebra and Logic
paper · doi:10.4230/dagsemproc.06111.2
We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of the Dagstuhl seminar "Complexity of Boolean Functions" held in March 2006, we introduce the different topics that have been discussed there and mention some of the major achievements. The summary closes with an outlook on the development of discrete computational complexity in the future.