License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.2
URN: urn:nbn:de:0030-drops-8409
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/840/
Go to the corresponding Portal

Krause, Matthias ; van Melkebeek, Dieter ; Pudlák, Pavel ; Reischuk, Rüdiger

06111 Executive Summary -- Complexity of Boolean Functions

pdf-format:
BoolFunc06ExSum.840.pdf (0.10 MB)

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:DagSemProc.06111.2,
  author =	{Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger},
  title =	{{06111 Executive Summary – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/840},
  URN =		{urn:nbn:de:0030-drops-8409},
  doi =		{10.4230/DagSemProc.06111.2},
  annote =	{Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning}
}

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
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 08.12.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI