• DocumentCode
    3395765
  • Title

    Coding for computing

  • Author

    Orlitsky, Alon ; Roche, James R.

  • Author_Institution
    AT&T Bell Labs., Murray Hill, NJ, USA
  • fYear
    1995
  • fDate
    23-25 Oct 1995
  • Firstpage
    502
  • Lastpage
    511
  • 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; encoding; coding; conditional entropy; naturally defined graph; Communication standards; Distortion measurement; Entropy; Information theory; Random variables; Rate-distortion; Robustness; Sorting; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
  • Conference_Location
    Milwaukee, WI
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-7183-1
  • Type

    conf

  • DOI
    10.1109/SFCS.1995.492580
  • Filename
    492580
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3395765