## Abstract

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ε2(1·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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022 |

Editors | Amit Chakrabarti, Chaitanya Swamy |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772495 |

DOIs | |

State | Published - Sep 1 2022 |

Event | 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022 - Virtual, Urbana-Champaign, United States Duration: Sep 19 2022 → Sep 21 2022 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 245 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022 |
---|---|

Country/Territory | United States |

City | Virtual, Urbana-Champaign |

Period | 9/19/22 → 9/21/22 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Sublinear time algorithms
- asymptotically optimal bounds
- h-index
- lower bounds
- subgraph counting