  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. En route, we also illustrate a localized version of our
fine-grained reduction.
  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.
