摘要: A sender communicates with a receiver who wishes to reliably evaluate function of their combined data. We show that if only the can transmit, number bits required is conditional entropy naturally defined graph. also determine needed when communicators exchange two messages. Reference made results rate distortion in evaluating random variables.
acm.org
sci-hub.se 参考文章(20)
Gábor Simonyi, Graph entropy: A survey. Combinatorial Optimization. pp. 399- 441 ,(1993)
J. Radhakrishnan, Better bounds for threshold formulas [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. pp. 314- 323 ,(1991) , 10.1109/SFCS.1991.185384
Toby Berger, Rate distortion theory : a mathematical basis for data compression Prentice-Hall. ,(1971)
I. Newman, P. Ragde, A. Wigderson, Perfect hashing, graph entropy, and circuit complexity structure in complexity theory annual conference. pp. 91- 99 ,(1990) , 10.1109/SCT.1990.113958
I. Csiszár, J. Körner, L. Lovász, K. Marton, G. Simonyi, ENTROPY SPLITTING FOR ANTIBLOCKING CORNERS AND -PERFECT GRAPHS Combinatorica. ,vol. 10, pp. 27- 40 ,(1990) , 10.1007/BF02122693
CE Shennon, Warren Weaver, A mathematical theory of communication Bell System Technical Journal. ,vol. 27, pp. 379- 423 ,(1948) , 10.1002/J.1538-7305.1948.TB01338.X
Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report) symposium on the theory of computing. pp. 209- 213 ,(1979) , 10.1145/800135.804414
A. Kaspi, T. Berger, Rate-distortion for correlated sources with partially separated encoders IEEE Transactions on Information Theory. ,vol. 28, pp. 828- 840 ,(1982) , 10.1109/TIT.1982.1056586
Jénos Körner, Fredman-Kolmo´s bounds and information theory Siam Journal on Algebraic and Discrete Methods. ,vol. 7, pp. 560- 570 ,(1986) , 10.1137/0607062
Michael L. Fredman, János Komlós, On the Size of Separating Systems and Families of Perfect Hash Functions Siam Journal on Algebraic and Discrete Methods. ,vol. 5, pp. 61- 68 ,(1984) , 10.1137/0605009