Show simple item record

dc.contributor.authorThurmer, Kateen_US
dc.date.accessioned2017-04-13T01:56:11Z
dc.date.issued2014
dc.date.submitted2014
dc.identifier.urihttps://hdl.handle.net/2144/21263
dc.descriptionThesis (M.Sc.Eng.) PLEASE NOTE: Boston University Libraries did not receive an Authorization To Manage form for this thesis or dissertation. It is therefore not openly accessible, though it may be available by request. If you are the author or principal advisor of this work and would like to request open access for it, please contact us at open-help@bu.edu. Thank you.en_US
dc.description.abstractThis 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.en_US
dc.language.isoen_US
dc.publisherBoston Universityen_US
dc.subjectComputer engineeringen_US
dc.subjectElectrical engineeringen_US
dc.subjectInteractive communicationen_US
dc.subjectThree-party protocolen_US
dc.titleWorst case interactive communication among three partiesen_US
dc.typeThesis/Dissertationen_US
dc.description.embargo2031-01-01
etd.degree.nameMaster of Science in Engineeringen_US
etd.degree.levelmastersen_US
etd.degree.disciplineComputer Engineeringen_US
etd.degree.grantorBoston Universityen_US


This item appears in the following Collection(s)

Show simple item record