Characterizing shapes of high-dimensional objects via Ricci curvatures plays a critical role in many research areas in mathematics and physics. However, even though several discretizations of Ricci curvatures for discrete combinatorial objects such as networks have been proposed and studied by mathematicians, the computational complexity aspects of these discretizations have escaped the attention of theoretical computer scientists to a large extent. In this paper, we study one such discretization, namely the Ollivier-Ricci curvature, from the perspective of efficient computation by fine-grained reductions and local query-based algorithms. Our main contributions are the following. (a) We relate our curvature computation problem to minimum weight perfect matching problem on complete bipartite graphs via fine-grained reduction. (b) We formalize the computational aspects of the curvature computation problems in suitable frameworks so that they can be studied by researchers in local algorithms. (c) We provide the first known lower and upper bounds on queries for query-based algorithms for the curvature computation problems in our local algorithms framework. We believe that our results bring forth an intriguing set of research questions, motivated both in theory and practice, regarding designing efficient algorithms for curvatures of objects.
翻译:通过Ricci curvature 来描述高维物体的形状,在数学和物理的许多研究领域发挥着关键的作用。然而,尽管数学家已经提出并研究了网络等离散组合物体的Ricci 曲线的几种离散特性,但是这些离散物体的计算复杂性在很大程度上没有引起理论计算机科学家的注意。在本文中,我们从精细的降级和地方基于查询的算法的有效计算角度来研究一种这种离散的特性,即Oliviier-Ricci curvoration。我们的主要贡献如下。 (a) 我们把我们的曲线计算问题与完整的双部分图形的最小重量完全匹配问题联系起来,通过微分缩略图的减少。 (b) 我们把曲线计算问题的计算方面正式化为合适的框架,以便研究人员可以在本地算法中研究这些问题。 (c) 我们提供了第一个已知的较低和上层的查询,用于查询我们本地算法的曲线计算问题。 我们认为,我们从研究的角度设计了一种高效的算法。