JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • Theses & Dissertations
    • Boston University Theses & Dissertations
    • View Item
    •   OpenBU
    • Theses & Dissertations
    • Boston University Theses & Dissertations
    • View Item

    Worst case interactive communication among three parties

    Thumbnail
    Download/View
    Thurmer_Kate_2...pdf (293.9Kb)
    Date Issued
    2014
    Author
    Thurmer, Kate
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Embargoed until:
    2030-12-31
    Permanent Link
    https://hdl.handle.net/2144/21263
    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.
    Description
    Thesis (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.
    Collections
    • Boston University Theses & Dissertations [4374]

    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Contact Us | Send Feedback | Help