Title :
Coding for computing
Author :
Orlitsky, Alon ; Roche, James R.
Author_Institution :
AT&T Bell Labs., Murray Hill, NJ, USA
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;
Conference_Titel :
Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
Conference_Location :
Milwaukee, WI
Print_ISBN :
0-8186-7183-1
DOI :
10.1109/SFCS.1995.492580
