Cover Image

Near-Optimality for Single-Source Personalized PageRank

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jiang, Xinpeng, Liu, Haoyu, Luo, Siqiang, Xiao, Xiaokui
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

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

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

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

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

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

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

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

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

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

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

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
by: Sajith, Thejas Radhika
Published: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
by: Dell, Holger, et al.
Published: (2022)

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
by: Sun, Yinqi
Published: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
by: Wallisch, Christian, et al.
Published: (2025)

Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up
by: Nakamura, Kengo, et al.
Published: (2024)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
by: Balzereit, Kaja, et al.
Published: (2024)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Cluster Editing on Cographs and Related Classes
by: Lafond, Manuel, et al.
Published: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
by: Chia, Nai-Hui, et al.
Published: (2025)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
by: Liu, Wei, et al.
Published: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
by: Gopalan, Parikshit, et al.
Published: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
by: Kurpisz, Adam, et al.
Published: (2026)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
by: Dvijotham, Krishnamurthy, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Optimality of Frequency Moment Estimation
by: Braverman, Mark, et al.
Published: (2024)