Graph-Theoretic Limits of Distributed Computation: Entropy, Eigenvalues, and Chromatic Numbers

Area of Science:

• Information Theory
• Distributed Systems
• Graph Theory

Background:

• Distributed computation of functions from correlated sources presents significant challenges.
• Exploiting the structure of computation tasks is key to efficient information processing.

Purpose of the Study:

• To develop novel coding strategies for distributed computation of arbitrary functions.
• To establish theoretical bounds on the optimal rates for lossless computation.
• To leverage graph theory and spectral methods for characterizing computation structures.

Main Methods:

• Utilizing source characteristic graphs and their n-fold OR products.
• Establishing bounds on optimal rates using chromatic entropy for graph products.
• Analyzing d-regular graphs and their connection to expansion rates via graph spectra.
• Applying the Gershgorin Circle Theorem (GCT) for spectral characterization of general graphs.

Main Results:

• Derived bounds on optimal rates for asymptotically lossless computation over finite fields.
• Provided an exact characterization of chromatic numbers for cycle graphs.
• Established connections between d-regular graphs, expansion rates, and graph spectra.
• Developed new bounds on optimal rates for general graphs using GCT and spectral analysis.

Conclusions:

• Graph-based coding and spectral analysis offer powerful tools for distributed computation.
• The proposed methods provide new insights into optimizing rates for complex computational tasks.
• The framework enables efficient and asymptotically lossless computation of arbitrary functions.