Can I read Lower Bounds in Communication Complexity: A Survey on EtoBox?

Lower Bounds in Communication Complexity: A Survey by Lee T., Shraibman A. is a nonfiction available to read on EtoBox.

What is Lower Bounds in Communication Complexity: A Survey about?

Из серии Foundations and Trends in Theoretical Computer Science издательства NOWPress, 2009, -127 pp. We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools. Communication complexity studies how much communication is needed in order to evaluate a function whose output depends on information distributed amongst two or more parties. Yao introduced an elegant mathematical framework for the study of communication complexity, applicable in numerous situations, from an email conversation between two people, to processors communicating on a chip. Indeed, the applicability of communication complexity to other areas, including circuit and formula complexity, VLSI design, proof complexity, and streaming algorithms, is one reason why it has attracted so much study.

Who reads Lower Bounds in Communication Complexity: A Survey?

Author

Lee T., Shraibman A.

Language

EN

Category

nonfiction

Subjects

Computer Science, Mathematics, Algorithms And Data Structures