Copyright
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8409
URL: http://drops.dagstuhl.de/opus/volltexte/2006/840/
Krause, Matthias ; van Melkebeek, Dieter ; Pudlák, Pavel ; Reischuk, Rüdiger

06111 Executive Summary -- Complexity of Boolean Functions

pdf-format:
Dokument 1.pdf (98 KB)

Abstract

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.

BibTeX - Entry

@InProceedings{krause_et_al:DSP:2006:840,
  author =	{Matthias Krause and Dieter van Melkebeek and Pavel Pudl{\'a}k and R{\"u}diger Reischuk},
  title =	{06111 Executive Summary -- Complexity of Boolean Functions},
  booktitle =	{Complexity of Boolean Functions},
  year =	{2006},
  editor =	{Matthias Krause and Pavel Pudl{\'a}k and R{\"u}diger Reischuk and Dieter van Melkebeek},
  number =	{06111},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/840},
  annote =	{Keywords: Boolean and quantum circuits,  discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, }
}

Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity,
Freie Schlagwörter (deutsch): randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning
Seminar: 06111 - Complexity of Boolean Functions
Documenttype: InProceedings
Issue date: 2006
Date of publication: 08.12.2006

DROPS-Home | Fulltext Search | Imprint Published by LZI