How large a fraction of a graph must one explore to approximate a quantity that depends on its global structure? This question underpins many algorithmic problems arising in modern large-scale networks, where several factors limit the access to the underlying graph topology. In the case of graph centrality measures, considerable effort has been devoted to approximating the score of a node with limited information about the rest of the graph; but for PageRank, a classic random-walk based centrality measure, no general solution was known until now. In this talk we present the first algorithm that approximates the PageRank score of any node in any graph by exploring only a sublinear number of nodes. We show that our result is essentially optimal, and that any combination of exploration primitives and error guarantees other than the one we use makes it impossible to achieve sub-linearity. This result proves that, for a specific but nontrivial class of Markov chains, the stationary probability of any given state can be approximated exploring only a vanishing portion of the transition matrix. This is a joint work with Enoch Peserico and Luca Pretto.