Cover Image

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Indyk, Piotr, Kapralov, Michael, Sheth, Kshiteej, Wagner, Tal
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

Provable Quantization with Randomized Hadamard Transform
by: Feng, Ying, et al.
Published: (2026)

Streaming Attention Approximation via Discrepancy Theory
by: Kochetkova, Ekaterina, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

New Bounds for Kernel Sums via Fast Spherical Embeddings
by: Wagner, Tal
Published: (2026)

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
by: Wolfson, Daniel, et al.
Published: (2026)

Learning from End User Data with Shuffled Differential Privacy over Kernel Densities
by: Wagner, Tal
Published: (2025)

A Bi-metric Framework for Fast Similarity Search
by: Xu, Haike, et al.
Published: (2024)

SpEx: A Spectral Approach to Explainable Clustering
by: Argov, Tal, et al.
Published: (2025)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
by: Musco, Cameron, et al.
Published: (2024)

Testing Noise Assumptions of Learning Algorithms
by: Goel, Surbhi, et al.
Published: (2025)

A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution
by: Chaudhry, Zan
Published: (2024)

Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors
by: Chatziafratis, Vaggos, et al.
Published: (2023)

MACKO: Sparse Matrix-Vector Multiplication for Low Sparsity
by: Macko, Vladimír, et al.
Published: (2025)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
by: Dehghankar, Mohsen, et al.
Published: (2024)

RSR-core: A High-Performance Engine for Low-Bit Matrix-Vector Multiplication
by: Dehghankar, Mohsen, et al.
Published: (2026)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Graph-based Nearest Neighbors with Dynamic Updates via Random Walks
by: Mishra, Nina, et al.
Published: (2025)

Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms
by: Li, Yi, et al.
Published: (2024)

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

OpenTensor: Reproducing Faster Matrix Multiplication Discovering Algorithms
by: Sun, Yiwen, et al.
Published: (2024)

Orthogonal Nonnegative Matrix Factorization with Sparsity Constraints
by: Basiri, Salar, et al.
Published: (2022)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

Matroid Algorithms Under Size-Sensitive Independence Oracles
by: Banihashem, Kiarash, et al.
Published: (2026)

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

Graph-Based Algorithms for Diverse Similarity Search
by: Anand, Piyush, et al.
Published: (2025)

Improving Online Algorithms via ML Predictions
by: Kumar, Ravi, et al.
Published: (2024)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
by: Angelopoulos, Spyros, et al.
Published: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
by: Klivans, Adam R., et al.
Published: (2024)

Masked Matrix Multiplication for Emergent Sparsity
by: Wheatman, Brian, et al.
Published: (2024)

Optimal Kernel Orchestration for Tensor Programs with Korch
by: Hu, Muyan, et al.
Published: (2024)

Near-Optimal Algorithms for Omniprediction
by: Okoroafor, Princewill, et al.
Published: (2025)

Dynamic Similarity Graph Construction with Kernel Density Estimation
by: Laenen, Steinar, et al.
Published: (2025)

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

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

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
by: Kapralov, Michael, et al.
Published: (2024)