Die Komplexität der Kommunikation

Alexander A. Razborov ()
Additional contact information
Alexander A. Razborov: The University of Chicago, Department of Computer Science

A chapter in Eine Einladung in die Mathematik, 2013, pp 99-119 from Springer

Abstract: Zusammenfassung Als ich gebeten wurde, für dieses Buch einen Artikel über etwas aus meinem Forschungsgebiet zu schreiben, musste ich sofort an Kommunikationskomplexität denken. Dieses trotz seiner Einfachheit sehr schöne und wichtige Teilgebiet der Komplexitätstheorie beschäftigt sich mit der Frage, wie viel Kommunikation zur Bestimmung eines bestimmten Ergebnisses zwischen mehreren Beteiligten nötig ist. Wir werden das grundlegende Kommunikationsmodell einführen und einige klassische Ergebnisse geben, teilweise sogar mit Beweis. Danach betrachten wir eine Variante, in der die Spieler gerechte Münzen werfen können. Wir schließen mit einigen anspruchsvolleren Modellen, über die man bis jetzt noch nicht allzu viel weiß. Alle Definitionen, Aussagen und Beweise sind komplett elementar, und doch können wir offene Fragen angeben, die selbst die besten Forscher seit Jahrzehnten nicht beantworten können.

Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-25798-8_8

Ordering information: This item can be ordered from
http://www.springer.com/9783642257988

DOI: 10.1007/978-3-642-25798-8_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().