The h-index is a metric used to measure the impact of a user in a publication setting, such as a
member of a social network with many highly liked posts or a researcher in an academic domain
with many highly cited publications. Specifically, the h-index of a user is the largest integer h such
that at least h publications of the user have at least h units of positive feedback.
We design an algorithm that, given query access to the n publications of a user and each
publication’s corresponding positive feedback number, outputs a (1±ε)-approximation of the h-index
of this user with probability at least 1 − δ in time O(n·ln (1/δ)/ε^2·h), where h is the actual h-index which
is unknown to the algorithm a-priori. We then design a novel lower bound technique that allows us
to prove that this bound is in fact asymptotically optimal for this problem in all parameters
n, h, ε, and δ.
Our work is one of the first in sublinear time algorithms that addresses obtaining asymptotically
optimal bounds, especially in terms of the error and confidence parameters. As such, we focus
on designing novel techniques for this task. In particular, our lower bound technique seems quite
general – to showcase this, we also use our approach to prove an asymptotically optimal lower bound
for the problem of estimating the number of triangles in a graph in sublinear time, which now is
also optimal in the error and confidence parameters. This latter result improves upon prior lower
bounds of Eden, Levi, Ron, and Seshadhri (FOCS’15) for this problem, as well as multiple follow-up
works that extended this lower bound to other subgraph counting problems.