Communication Complexity

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

A chapter in An Invitation to Mathematics, 2011, pp 97-117 from Springer

Abstract: Abstract When I was asked to write a contribution for this book about something related to my research, I immediately thought of communication complexity. This relatively simple but extremely beautiful and important sub-area of complexity theory studies the amount of communication needed for several distributed parties to learn something new. We will review the basic communication model and some of the classical results known for it, sometimes even with proofs. Then we will consider a variant in which the players are allowed to flip fair unbiased coins. We will finish with a brief review of more sophisticated models in which our current state of knowledge is less than satisfactory. All our definitions, statements and proofs are completely elementary, and yet we will state several open problems that have evaded strong researchers for decades.

Keywords: Complexity Theory; Communication Complexity; Binary String; Coin Toss; Communication Matrix (search for similar items in EconPapers)
Date: 2011
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-19533-4_8

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

DOI: 10.1007/978-3-642-19533-4_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 ().