Search T-Space Advanced Search
Home

Browse
Communities
& Collections

Issue Date
Author
Title
Subject

Sign on to:
Receive email
updates

My Account
authorized users

Edit Profile

Help
About T-Space
 Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/24736

 Title: Multiparty Communication Complexity Authors: David, Matei Advisor: Pitassi, Toniann Department: Computer Science Keywords: communication complexitynumber on foreheadclass separationdeterminismrandomizationnondeterminismstack machineslower bound Issue Date: 6-Aug-2010 Abstract: Communication complexity is an area of complexity theory that studies an abstract model of computation called a communication protocol. In a $k$-player communication protocol, an input to a known function is partitioned into $k$ pieces of $n$ bits each, and each piece is assigned to one of the players in the protocol. The goal of the players is to evaluate the function on the distributed input by using as little communication as possible. In a Number-On-Forehead (NOF) protocol, the input piece assigned to each player is metaphorically placed on that player's forehead, so that each player sees everyone else's input but its own. In a Number-In-Hand (NIH) protocol, the piece assigned to each player is seen only by that player. Overall, the study of communication protocols has been used to obtain lower bounds and impossibility results for a wide variety of other models of computation. Two of the main contributions presented in this thesis are negative results on the NOF model of communication, identifying limitations of NOF protocols. Together, these results consitute stepping stones towards a better fundamental understanding of this model. As the first contribution, we show that randomized NOF protocols are exponentially more powerful than deterministic NOF protocols, as long as $k \le n^c$ for some constant $c$. As the second contribution, we show that nondeterministic NOF protocols are exponentially more powerful than randomized NOF protocols, as long as $k \le \delta \cdot \log n$ for some constant $\delta < 1$. For the third major contribution, we turn to the NIH model and we present a positive result. Informally, we show that a NIH communication protocol for a function $f$ can simulate a Stack Machine (a Turing Machine augmented with a stack) for a related function $F$, consisting of several instances of $f$ bundled together. Using this simulation and known communication complexity lower bounds, we obtain the first known (space vs. number of passes) trade-off lower bounds for Stack Machines. URI: http://hdl.handle.net/1807/24736 Appears in Collections: DoctoralDepartment of Computer Science - Doctoral theses

Files in This Item:

File Description SizeFormat
David_Matei__201006_PhD_thesis.pdf890.47 kBAdobe PDF
View/Open

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.