Distributed Compression for Computation and Bounds on the Optimal Rate

Mohammad Reza Deylam Salehi, Derya Malak · 2025

Read Distributed Compression for Computation and Bounds on the Optimal Rate by Mohammad Reza Deylam Salehi, Derya Malak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-15706.txt.

Introduction

Mohammad Reza Deylam Salehi and Derya Malak study how cheaply two far-apart nodes can compute a function of their data, in this 2025 paper. Each node holds one of two correlated sources, and a receiver wants a function of both, computed almost without loss. The trick is to code the structure of the task itself, using characteristic graphs that capture which inputs must stay distinguishable.

The authors bound the best possible rate, expressed through the chromatic entropy of repeated graph products, for regular graphs and for general graphs. For cycle graphs they pin down the exact chromatic numbers and matching rate bounds. For wider classes of regular graphs they connect graph spectra to how fast the repeated products expand. For general graphs they use the Gershgorin Circle Theorem to describe the spectra and build rate bounds. The codes, they argue, compress the computation's structure in a succinct new way.

Catalog record

CREATORMohammad Reza Deylam Salehi, Derya Malak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-15706

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Compression for Computation and Bounds on the Optimal Rate Mohammad Reza Deylam Salehi, Derya Malak Abstract We address the problem of distributed computation of arbitrary functions of two correlated sources X 1 X_{1} and X 2 X_{2} , residing in two distributed source nodes, respectively. We exploit the structure of a computation task by coding source characteristic graphs (and multiple instances using the n n -fold OR product of this graph with itself). For regular graphs and general graphs, we establish bounds on the optimal rate—characterized by the chromatic entropy for the n n -fold graph products—that allows a receiver for asymptotically lossless computation of arbitrary functions over finite fields. For the special class of cycle graphs (i.e., 2 2 -regular graphs), we establish an exact characterization of chromatic numbers and derive bounds on the required rates. Next, focusing on the more general class of d d -regular graphs, we establish connections between d d -regular graphs and expansion rates for n n -fold graph powers using graph spectra. Finally, for general graphs, we leverage the Gershgorin Circle Theorem (GCT) to provide a characterization of the spectra, which allows us to build new bounds on the optimal rate. Our codes leverage the spectra of the computation and provide a graph expansion-based characterization to efficiently/succinctly capture the computation structure, providing new insights into the problem of distributed computation of arbitrary functions. I Introduction Data compression is the process of using fewer bits than the original size of the source, which is given by Shannon’s entropy of a source [ 2 ] in the case of a point-to-point communication model. In the setting of distributed sources, where the goal is to recover them jointly at a receiver, the Slepian-Wolf theorem gives the fundamental limits of rate for compression [ 3 ] . In the case when the receiver wants to compute a deterministic function of distributed sources, a further reduction in compression is possible via accounting for the structure of the function as well as the structure of the joint source distribution [ 4 ] . This approach is known as distributed functional compression, in which a function represents an abstraction of a particular task, the sources separately compress their data and send color encodings of their data to a common receiver, and the receiver, from the obtained colors, recovers the desired function of the sources. This approach differs from the conventional approach [ 3 ] , where the receiver jointly decodes source sequences. I-A Motivation and Literature Review Let us begin with an example. Consider a college student database with information including the rental records, demographics and health of individuals. The Ministry of Science wants to offer housing aid to a particular group of students by requiring information solely on the rental contracts and payslips of the students, and without disclosing their personal data, due to privacy and redundancy constraints. In data compression, storing and sending a stream of data that is not always required is not practical from the perspectives of storage and transmission. The scenario of student housing is an example of realizing functional compression, which avoids compressing and transmitting large volumes of all available data, and is instead tailored to the specifics of the function, i.e., a student’s eligibility for getting housing aid or not. In Shannon’s breakthrough work in [ 2 ] , the function to be recovered at the receiver is the identity function of the source variable, i.e., the source itself. Generalizing the noiseless coding of a discrete information source, given in [ 2 ] , to distributed compression and joint decoding of two jointly distributed and finite alphabet X_{1} and X_{2} , Slepian-Wolf theorem gives a theoretical lower bound for the lossless coding rate of distributed coding of such sources [ 3 ] , where the two data sequences of memoryless correlated sources with finite alphabets {\bf X}_{1}^{n} , and {\bf X}_{2}^{n} are obtained by n repeated independent drawings from a discrete bivariate distribution. Practical implementation schemes for Slepian-Wolf compression have been proposed, including [ 5 , 6 , 7 ] . In functional compression of distributed sources X_{1} , and X_{2} , however, the goal is to compress the sources separately while ensuring that a deterministic function f(X_{1},X_{2}) of these sources can be calculated by a user. Prior attempts on functional compression can be categorized into works focusing on lossless and zero error compression of functions, [ 8 , 2 , 4 , 9 , 10 , 3 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 ] , and those for which the compression schemes tolerate distortion for lossy reconstruction [ 24 , 25 , 26 , 27 , 28 , 29 , 30 ] . Several special cases of distributed compression have been studied. In [ 15 ] , Ahlswede and Körner have determined the rate region for a distributed compression setting where separate encoders encode the n -th realizations of correlated sources X_{1} and X_{2} observed by sources one and two respectively, and a receiver aims to only recover {\bf X}_{2}^{n} . Körner and Marton, in [ 14 ] , have dealt with the problem of distributed encoding of two binary sources X_{1} and X_{2} to compute their modulo-two sum, i.e., f(X_{1},X_{2})=(X_{1}+X_{2})\mod 2 , at the receiver. In [ 26 ] , Yamamoto has extended the Wyner-Ziv model [ 24 ] , which has addressed lossy source coding with side information at the decoder, to a setting where the decoder estimates a function f(X_{1},X_{2}) of the source X_{1} given side information X_{2} . In [ 17 ] , Han and Kobayashi have established an achievable distributed functional reconstruction scheme, which depends on the structure of f(X_{1},X_{2}) , and the joint distribution of (X_{1},X_{2}) . Building on [ 26 ] , optimal coding schemes and achievable rate regions have been derived for lossless and lossy compression of source X_{1} for distributed computation of f(X_{1},X_{2}) given side information X_{2} [ 11 , 31 , 10 , 32 ] , for distributed compression of sources X_{1} and X_{2} for the computation of f(X_{1},X_{2}) [ 12 , 33 ] . More specifically, in [ 11 ] , Orlitsky and Roche have provided a single letter characterization for general functions of two variables using the notion of source characteristic graphs (confusion graphs) introduced by Körner [ 34 ] , where the vertices are the possible realizations of a source and the edges capture the function structure. I-B Overview and Contributions In this work, we design a coding framework for the problem of distributed functional compression with two distributed sources having access to X_{1} and X_{2} , respectively, each with a finite alphabet, and a receiver that wants to reconstruct the function f(X_{1},X_{2}) in an asymptotically lossless manner. To capture the structure of the function f in compression, we exploit the notion of source characteristic graphs . Given source variable X_{1} , the limits of color reuse are determined by chromatic numbers \chi(G) [ 23 ] 1 1 1 In [ 23 ] , Witsenhausen has considered zero-error compression using characteristic graphs with side information. , and the

Read the complete text