English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Characterizing shapes of high-dimensional objects via Ricci curvatures playsa critical role in many research areas in mathematics and physics. However,even though several discretizations of Ricci curvatures for discretecombinatorial objects such as networks have been proposed and studied bymathematicians, the computational complexity aspects of these discretizationshave escaped the attention of theoretical computer scientists to a largeextent. In this paper, we study one such discretization, namely theOllivier-Ricci curvature, from the perspective of efficient computation byfine-grained reductions and local query-based algorithms. Our maincontributions are the following.  (a) We relate our curvature computation problem to minimum weight perfectmatching problem on complete bipartite graphs via fine-grained reduction.  (b) We formalize the computational aspects of the curvature computationproblems in suitable frameworks so that they can be studied by researchers inlocal algorithms.  (c) We provide the first known lower and upper bounds on queries forquery-based algorithms for the curvature computation problems in our localalgorithms framework. En route, we also illustrate a localized version of ourfine-grained reduction.  We believe that our results bring forth an intriguing set of researchquestions, motivated both in theory and practice, regarding designing efficientalgorithms for curvatures of objects.

On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions