• DocumentCode
    1464795
  • Title

    Coding for computing

  • Author

    Orlitsky, Alon ; Roche, James R.

  • Author_Institution
    Dept. of Electr. & Comput. Eng., California Univ., San Diego, La Jolla, CA, USA
  • Volume
    47
  • Issue
    3
  • fYear
    2001
  • fDate
    3/1/2001 12:00:00 AM
  • Firstpage
    903
  • Lastpage
    917
  • Abstract
    A sender communicates with a receiver who wishes to reliably evaluate a function of their combined data. We show that if only the sender can transmit, the number of bits required is a conditional entropy of a naturally defined graph. We also determine the number of bits needed when the communicators exchange two messages
  • Keywords
    communication complexity; entropy codes; coding; combined data; communication-complexity; computing; conditional entropy; graph; message exchange; random variables; receiver; sender; Communication standards; Complexity theory; Distortion measurement; Entropy; National security; Protocols; Random variables; Rate-distortion; Sorting; Upper bound;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/18.915643
  • Filename
    915643
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1464795