08381 Executive Summary – Computational Complexity of Discrete Problems

Authors Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, Dieter van Melkebeek



PDF
Thumbnail PDF

File

DagSemProc.08381.2.pdf
  • Filesize: 103 kB
  • 7 pages

Document Identifiers

Author Details

Peter Bro Miltersen
Rüdiger Reischuk
Georg Schnitger
Dieter van Melkebeek

Cite AsGet BibTex

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/DagSemProc.08381.2

Abstract

Estimating the computational complexity of discrete problems constitutes 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 relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.
Keywords
  • Computational complexity
  • discrete problems
  • Turing machines
  • circuits
  • proof complexity
  • pseudorandomness
  • derandomization
  • cryptography
  • computational learning
  • communication complexity
  • query complexity
  • hardness of approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail