Cover Image

Instance-Optimality in PageRank Computation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Thorup, Mikkel, Wang, Hanzhi
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Revisiting Local Computation of PageRank: Simple and Optimal
by: Wang, Hanzhi, et al.
Published: (2024)

Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal
by: Wang, Hanzhi
Published: (2024)

Efficient Algorithms for Personalized PageRank Computation: A Survey
by: Yang, Mingji, et al.
Published: (2024)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Personalized PageRank Estimation in Undirected Graphs
by: Bertram, Christian, et al.
Published: (2026)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Near-Optimality for Single-Source Personalized PageRank
by: Jiang, Xinpeng, et al.
Published: (2025)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Approximating Single-Source Personalized PageRank with Absolute Error Guarantees
by: Wei, Zhewei, et al.
Published: (2024)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
by: Jin, Wenyu, et al.
Published: (2024)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
by: Fountoulakis, Kimon, et al.
Published: (2026)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs
by: Li, Zihao, et al.
Published: (2024)

Optimal Dynamic Parameterized Subset Sampling
by: Gan, Junhao, et al.
Published: (2024)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
by: Abrahamsen, Mikkel
Published: (2024)

Unifying Laplace Mechanism with Instance Optimality in Differential Privacy
by: Durfee, David
Published: (2025)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Towards Optimal Robustness in Learning-Augmented Paging
by: Chen, Peng, et al.
Published: (2026)

Fun Maximizing Search, (Non) Instance Optimality, and Video Games for Parrots
by: Barbay, Jérémy
Published: (2024)

Non-Linear Paging
by: Doron-Arad, Ilan, et al.
Published: (2024)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
by: Chakraborty, Diptarka, et al.
Published: (2026)

New and Improved Bounds for Markov Paging
by: Pabbaraju, Chirag, et al.
Published: (2025)

Instance-Optimal Uniformity Testing and Tracking
by: Blanc, Guy, et al.
Published: (2025)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
by: Zhao, Zhuowei, et al.
Published: (2025)

Modeling Online Paging in Multi-Core Systems
by: Mari, Mathieu, et al.
Published: (2024)

Computing Experiment-Constrained D-Optimal Designs
by: Pillai, Aditya, et al.
Published: (2024)

Instance and Universally Optimal Bounds for Imprecise Pareto Fronts
by: de Berg, Sarita, et al.
Published: (2026)

An Improved Algorithm for Sparse Instances of SAT
by: Jain, Sanjay, et al.
Published: (2024)