2026-08-18T09:31:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:840 2024-03-06T11:06:45Z ddc:004 open_access

06111 Executive Summary – Complexity of Boolean Functions Krause, Matthias van Melkebeek, Dieter Pudlák, Pavel Reischuk, Rüdiger Boolean and quantum circuits discrete problems computational complexity lower bounds communication complexity proof and query complexity randomization pseudo-randomness derandomization approximation cryptography computational learning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matthias Krause and Dieter van Melkebeek and Pavel Pudlák and Rüdiger Reischuk 2006 Is Part Of Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06111.2 urn:nbn:de:0030-drops-8409 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2 eng https://creativecommons.org/licenses/by/4.0/legalcode