Cover Image

A Faster Generalized Two-Stage Approximate Top-K

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Samaga, Yashas, Yerram, Varun, Babbula, Spandana Raj, Jain, Prateek, Netrapalli, Praneeth
Format:	Preprint
Published:	2025
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM Inference
by: L, Yashas Samaga B, et al.
Published: (2024)

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method
by: Garg, Sachin, et al.
Published: (2025)

Online Two-Stage Submodular Maximization
by: Nikolaou, Iasonas, et al.
Published: (2025)

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
by: Kannan, Ravindran, et al.
Published: (2024)

Efficient Data Shapley for Weighted Nearest Neighbor Algorithms
by: Wang, Jiachen T., et al.
Published: (2024)

Faster Algorithms for Agnostically Learning Disjunctions and their Implications
by: Diakonikolas, Ilias, et al.
Published: (2025)

Faster and Space Efficient Indexing for Locality Sensitive Hashing
by: Verma, Bhisham Dev, et al.
Published: (2025)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
by: Jin, Yujia, et al.
Published: (2024)

Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
by: Balmaseda, Vicente, et al.
Published: (2024)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
by: Oettershagen, Lutz
Published: (2026)

Graph Neural Network-Informed Predictive Flows for Faster Ford-Fulkerson and PAC-Learnability
by: Wiesler, Eleanor, et al.
Published: (2026)

Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
by: Mangoubi, Oren, et al.
Published: (2024)

A Simple Approximation Algorithm for Optimal Decision Tree
by: Zhuo, Zhengjia, et al.
Published: (2025)

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

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

The Space Complexity of Approximating Logistic Loss
by: Dexter, Gregory, et al.
Published: (2024)

Approximation Algorithms for Combinatorial Optimization with Predictions
by: Antoniadis, Antonios, et al.
Published: (2024)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Dynamic Spectral Clustering with Provable Approximation Guarantee
by: Laenen, Steinar, et al.
Published: (2024)

Reweighted Solutions for Weighted Low Rank Approximation
by: Woodruff, David P., et al.
Published: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
by: McCauley, Samuel, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Windows
by: Yao, Ziqi, et al.
Published: (2025)

Improved Approximations for Hard Graph Problems using Predictions
by: Aamand, Anders, et al.
Published: (2025)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition
by: Fahrbach, Matthew, et al.
Published: (2025)

Fast White-Box Adversarial Streaming Without a Random Oracle
by: Feng, Ying, et al.
Published: (2024)

Sublinear Sketches for Approximate Nearest Neighbor and Kernel Density Estimation
by: Danait, Ved, et al.
Published: (2025)

Approximating splits for decision trees quickly in sparse data streams
by: Tatti, Nikolaj
Published: (2026)

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

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
by: Drexler, Lukas, et al.
Published: (2023)

Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
by: Woodruff, David P., et al.
Published: (2024)

Scaling Up Graph Propagation Computation on Large Graphs: A Local Chebyshev Approximation Approach
by: Yang, Yichun, et al.
Published: (2024)

Faster Private Minimum Spanning Trees
by: Pagh, Rasmus, et al.
Published: (2024)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)