分布式计算的图形理论极限:,自身价值和染色数
Mohammad Reza Deylam Salehi1, Derya Malak1
1Communication Systems Department, EURECOM, Sophia Antipolis, 06410 Biot, France.
Entropy (Basel, Switzerland)
|July 29, 2025
概括
本研究介绍了基于图的编码,用于从相关源计算函数的分布式计算. 使用图谱和格尔什戈林圆定理来推导最佳速率的新边界,以实现高效,无损计算.
科学领域:
- 信息理论 信息理论
- 分布式系统 分布式系统
- 图形理论 图形理论
背景情况:
- 来自相关源的函数的分布式计算带来了重大挑战.
- 利用计算任务的结构是有效处理信息的关键.
研究的目的:
- 开发用于任意函数分布式计算的新型编码策略.
- 为无损计算的最佳速率建立理论界限.
- 利用图形理论和光谱方法来描述计算结构.
主要方法:
- 使用源特征图和它们的n-fold OR产物.
- 用图形产品的染色来确定最佳速率的边界.
- 通过图谱分析d正规图及其与膨胀率的联系.
- 应用格尔什戈林圆定理 (GCT) 进行一般图的光谱表征.
主要成果:
- 在有限字段上进行非对称无损失计算的最佳速率的衍生边界.
- 为循环图提供了对色号的准确表征.
- 建立了d-正规图,扩张率和图谱之间的连接.
- 开发了使用GCT和光谱分析的一般图表的最佳率的新界限.
结论:
- 基于图的编码和光谱分析为分布式计算提供了强大的工具.
- 提出的方法为复杂的计算任务的优化率提供了新的见解.
- 该框架允许对任意函数进行高效且无对称的无损计算.
相关概念视频
Entropy Change in Reversible Processes
2.7K
In the Carnot engine, which achieves the maximum efficiency between two reservoirs of fixed temperatures, the total change in entropy is zero. The observation can be generalized by considering any reversible cyclic process consisting of many Carnot cycles. Thus, it can be stated that the total entropy change of any ideal reversible cycle is zero.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
2.7K
Probability Histograms
12.2K
A probability histogram is a visual representation of a probability distribution. Similar a typical histogram, the probability histogram consists of contiguous (adjoining) boxes. It has both a horizontal axis and a vertical axis. The horizontal axis is labeled with what the data represents. The vertical axis is labeled with probability. Each rectangular bar in the histogram is 1 unit wide, which suggests that the area under each bar equals the probability, P(x), where x is 1, 2, 3, and so on.
12.2K
Theorems of Pappus and Guldinus
2.1K
The two theorems developed by Pappus and Guldinus are widely used in mathematics, engineering, and physics to find the surface area and volume of any body of revolution. This is done by revolving a plane curve around an axis that does not intersect the curve to find its surface area or revolving a plane area around a non-intersecting axis to calculate its volume.
For finding the surface area, consider a differential line element that generates a ring with surface area dA when revolved.
For finding the surface area, consider a differential line element that generates a ring with surface area dA when revolved.
2.1K
Entropy and the Second Law of Thermodynamics
3.2K
The second law of thermodynamics can be stated quantitatively using the concept of entropy. Entropy is the measure of disorder of the system.
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
The relation between entropy and disorder can be illustrated with the example of the phase change of ice to water. In ice, the molecules are located at specific sites giving a solid state, whereas, in a liquid form, these molecules are much freer to move. The molecular arrangement has therefore become more randomized. Although the change in average...
3.2K
Central Limit Theorem
15.9K
The central limit theorem, abbreviated as clt, is one of the most powerful and useful ideas in all of statistics. The central limit theorem for sample means says that if you repeatedly draw samples of a given size and calculate their means, and create a histogram of those means, then the resulting histogram will tend to have an approximate normal bell shape. In other words, as sample sizes increase, the distribution of means follows the normal distribution more closely.
The sample size, n, that...
The sample size, n, that...
15.9K
Vector Algebra: Graphical Method
13.8K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
13.8K


