# Graph Coloring and Conditional Graph Entropy

Year
2006
Type(s)
Author(s)
V. Doshi, D. Shah, M. Medard, S. Jaggi
Source
2006 Fortieth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2006, pp. 2137-2141
Url
http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4176956

We consider the remote computation of a function of two sources where one is receiver side information. Specifically, given side information Y, we wish to compute f(X, Y) based on information transmitted by X over a noise-less channel. The goal is to characterize the minimal rate at which X must transmit information to enable the computation of the function f. Recently, Orlitsky and Roche (2001) established that the conditional graph entropy of the characteristic graph of the function is a solution to this problem. Their achievability scheme does not separate “functional coding” from the well understood distributed source coding problem. In this paper, we seek a separation between the functional coding and the coding for correlation. In other words, we want to preprocess X (with respect to f), and then transmit the preprocessed data using a standard Slepian-Wolf coding scheme at the Orlitsky-Roche rate. We establish that a minimum (conditional) entropy coloring of the product of characteristic graphs is asymptotically equal to the conditional graph entropy. This can be seen as a generalization of a result of Korner (1973) which shows that the minimum entropy coloring of product graphs is asymptotically equal to the graph entropy. Thus, graph coloring provides a modular technique to achieve coding gains when the receiver is interested in decoding some function of the source.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9041226,"math_prob":0.818364,"size":1396,"snap":"2022-40-2023-06","text_gpt3_token_len":274,"char_repetition_ratio":0.13433908,"word_repetition_ratio":0.018604651,"special_character_ratio":0.18553008,"punctuation_ratio":0.0746888,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9526796,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-01-26T23:13:11Z\",\"WARC-Record-ID\":\"<urn:uuid:e75e72e7-5109-422e-9abe-45d9c421d9af>\",\"Content-Length\":\"59845\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:aae27078-cfbc-4b71-a901-7f8ef0fc1039>\",\"WARC-Concurrent-To\":\"<urn:uuid:50cbc7d1-880c-413b-8a1a-60ddf42367a3>\",\"WARC-IP-Address\":\"18.9.62.54\",\"WARC-Target-URI\":\"https://devavrat.mit.edu/publications/graph-coloring-and-conditional-graph-entropy/\",\"WARC-Payload-Digest\":\"sha1:N3RRUTWBXB2IN4URGOXIQTEMTMCECM3B\",\"WARC-Block-Digest\":\"sha1:PWPP73G6MY4P27VRSAD3PNJZEGDYD4B6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-06/CC-MAIN-2023-06_segments_1674764494826.88_warc_CC-MAIN-20230126210844-20230127000844-00451.warc.gz\"}"}