Back to search

Boston University

Worst case interactive communication among three parties

Abstract

dc:description.abstract

This thesis extends existing work on worst-case two party interactive communication to three parties. PX, PY and PZ know random variables X, Y and Z, respectively, and all parties know the joint distribution, p(x; y; z). Using an agreed-upon protocol, the parties communicate over one or more error-free channels. The objective is for PZ to learn X and Y , and cost is measured in worst-case total information bits transmitted. In the two party case, where PZ must learn only X, interactive protocols (in which PZ may send bits) can reduce the cost to approximately the log of the cost when only PX may transmit (Orlitsky, 1990). In the three party case, PZ can learn X and Y separately, however this is not necessarily optimal. Can a three party protocol provide a cost savings over two separate two party protocols? We describe a joint protocol based on that of Naor et al. (Naor et al., 1993) for communicating X and Y in parallel and show that it can provide at most a constant factor savings. We also describe a sequential protocol in which PZ first learns Y and then uses this knowledge to reduce the cost of subsequently learning X. Although there are input distributions for which this type of protocol can provide more substantial savings, we show that for a large fraction of all input distributions, any three party protocol can provide at most a constant factor savings over two separate two party protocols. Finally, we increase the number of parties and show that for some input distributions multi-party interaction can yield a better than constant factor savings.

Degree

thesis:*
Name thesis:degree_name
Master of Science in Engineering
Level thesis:degree_level
masters
Discipline thesis:degree_discipline
Computer Engineering
Grantor dc:publisher
Boston University
Year dc:date.issued
2014

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Thurmer, Kate

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/21263

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Thurmer, Kate. Worst case interactive communication among three parties. masters thesis, Boston University, 2014. https://hdl.handle.net/2144/21263