Cover Image

New and Improved Bounds for Markov Paging

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pabbaraju, Chirag, Vakilian, Ali
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

Lower Bounds for Greedy Teaching Set Constructions
by: Compton, Spencer, et al.
Published: (2025)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
by: Charikar, Moses, et al.
Published: (2023)

A Characterization of List Regression
by: Pabbaraju, Chirag, et al.
Published: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
by: Pabbaraju, Chirag, et al.
Published: (2025)

Learning with Monotone Adversarial Corruptions
by: Larsen, Kasper Green, et al.
Published: (2026)

Pareto-optimal Non-uniform Language Generation
by: Charikar, Moses, et al.
Published: (2025)

Exploring Facets of Language Generation in the Limit
by: Charikar, Moses, et al.
Published: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
by: Garg, Sumegha, et al.
Published: (2026)

Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
by: Dong, Yinhao, et al.
Published: (2024)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

A Characterization of List Language Identification in the Limit
by: Charikar, Moses, et al.
Published: (2025)

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

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

The Sample Complexity of Replicable Realizable PAC Learning
by: Larsen, Kasper Green, et al.
Published: (2026)

On Socially Fair Low-Rank Approximation and Column Subset Selection
by: Song, Zhao, et al.
Published: (2024)

Scalable Algorithms for Individual Preference Stable Clustering
by: Mosenzon, Ron, et al.
Published: (2024)

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

Learning the Positions in CountSketch
by: Li, Yi, et al.
Published: (2023)

Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
by: Kaudan, Chirag, et al.
Published: (2026)

Guessing Efficiently for Constrained Subspace Approximation
by: Bhaskara, Aditya, et al.
Published: (2025)

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

Improving Pinwheel Density Bounds for Small Minimums
by: Mishra, Ahan, et al.
Published: (2025)

Learning-Based Algorithms for Graph Searching Problems
by: DePavia, Adela Frances, et al.
Published: (2024)

New Bounds for Circular Trace Reconstruction
by: Burudgunte, Arnav, et al.
Published: (2025)

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

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

Improved Lower Bounds for Privacy under Continual Release
by: Aryanfard, Bardiya, et al.
Published: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
by: Ghosh, Prantar, et al.
Published: (2024)

Bounds on Longest Simple Cycles in Weighted Directed Graphs via Optimum Cycle Means
by: Dasdan, Ali
Published: (2025)

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

Improved Bounds for Rectangular Monotone Min-Plus Product and Applications
by: Dürr, Anita
Published: (2022)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
by: Heineman, George T., et al.
Published: (2024)

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)