  We revisit the classic local graph exploration algorithm ApproxContributions
proposed by Andersen, Borgs, Chayes, Hopcroft, Mirrokni, and Teng (WAW '07,
Internet Math. '08) for computing an $\epsilon$-approximation of the PageRank
contribution vector for a target node $t$ on a graph with $n$ nodes and $m$
edges. We give a worst-case complexity bound of ApproxContributions as
$O(n\pi(t)/\epsilon\cdot\min(\Delta_{in},\Delta_{out},\sqrt{m}))$, where
$\pi(t)$ is the PageRank score of $t$, and $\Delta_{in}$ and $\Delta_{out}$ are
the maximum in-degree and out-degree of the graph, resp. We also give a lower
bound of
$\Omega(\min(\Delta_{in}/\delta,\Delta_{out}/\delta,\sqrt{m}/\delta,m))$ for
detecting the $\delta$-contributing set of $t$, showing that the simple
ApproxContributions algorithm is already optimal.
  We also investigate the computational complexity of locally estimating a
node's PageRank centrality. We improve the best-known upper bound of
$\widetilde{O}(n^{2/3}\cdot\min(\Delta_{out}^{1/3},m^{1/6}))$ given by Bressan,
Peserico, and Pretto (SICOMP '23) to
$O(n^{1/2}\cdot\min(\Delta_{in}^{1/2},\Delta_{out}^{1/2},m^{1/4}))$ by simply
combining ApproxContributions with the Monte Carlo simulation method. We also
improve their lower bound of
$\Omega(\min(n^{1/2}\Delta_{out}^{1/2},n^{1/3}m^{1/3}))$ to
$\Omega(n^{1/2}\cdot\min(\Delta_{in}^{1/2},\Delta_{out}^{1/2},m^{1/4}))$ if
$\min(\Delta_{in},\Delta_{out})=\Omega(n^{1/3})$, and to
$\Omega(n^{1/2-\gamma}(\min(\Delta_{in},\Delta_{out}))^{1/2+\gamma})$ if
$\min(\Delta_{in},\Delta_{out})=o(n^{1/3})$, where $\gamma>0$ is an arbitrarily
small constant. Our matching upper and lower bounds resolve the open problem of
whether one can tighten the bounds given by Bressan, Peserico, and Pretto (FOCS
'18, SICOMP '23). Remarkably, the techniques and analyses for proving all our
results are surprisingly simple.
