Abstract
The hindex 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 hindex 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 hindex of this user with probability at least 1δ in time O(n⋅ln(1/δ) / (ε²⋅h)), where h is the actual hindex which is unknown to the algorithm apriori. 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 followup works that extended this lower bound to other subgraph counting problems.
BibTeX  Entry
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2022.48,
author = {Assadi, Sepehr and Nguyen, HoaiAn},
title = {{Asymptotically Optimal Bounds for Estimating HIndex in Sublinear Time with Applications to Subgraph Counting}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
pages = {48:148:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772495},
ISSN = {18688969},
year = {2022},
volume = {245},
editor = {Chakrabarti, Amit and Swamy, Chaitanya},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17170},
URN = {urn:nbn:de:0030drops171708},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.48},
annote = {Keywords: Sublinear time algorithms, hindex, asymptotically optimal bounds, lower bounds, subgraph counting}
}
Keywords: 

Sublinear time algorithms, hindex, asymptotically optimal bounds, lower bounds, subgraph counting 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) 
Issue Date: 

2022 
Date of publication: 

15.09.2022 