Cover Image

Improved Sparse Recovery for Approximate Matrix Multiplication

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Uffenheimer, Yahel, Weinstein, Omri
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs
by: Ailon, Nir, et al.
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

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

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Hardness Amplification for Dynamic Binary Search Trees
by: Jiang, Shunhua, et al.
Published: (2024)

Discrepancy Minimization in Input-Sparsity Time
by: Deng, Yichuan, et al.
Published: (2022)

Output-Sparse Matrix Multiplication Using Compressed Sensing
by: Bennett, Huck, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

A Dynamic Low-Rank Fast Gaussian Transform
by: Huang, Baihe, et al.
Published: (2022)

Matrix Multiplication Reductions
by: Gola, Ashish, et al.
Published: (2024)

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
by: Zhao, Jingyang, et al.
Published: (2026)

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

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

Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication
by: Mutluergil, Kemal, et al.
Published: (2026)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)

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

Training Overparametrized Neural Networks in Sublinear Time
by: Deng, Yichuan, et al.
Published: (2022)

Matrix Multiplication Verification Using Coding Theory
by: Bennett, Huck, et al.
Published: (2023)

On the Complexity of Finding Approximate LCS of Multiple Strings
by: Hasibi, Hamed, et al.
Published: (2025)

$\ell_2/\ell_2$ Sparse Recovery via Weighted Hypergraph Peeling
by: Fischer, Nick, et al.
Published: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
by: Uhlmann, Jeffrey
Published: (2025)

Composition Orderings for Linear Functions and Matrix Multiplication Orderings
by: Kubo, Susumu, et al.
Published: (2024)

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
by: Schwartz, Oded, et al.
Published: (2025)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
by: Mallek, Nadym, et al.
Published: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

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

Improved Approximations for Flexible Network Design
by: Hyatt-Denesik, Dylan, et al.
Published: (2024)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
by: Abboud, Amir, et al.
Published: (2023)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
by: Indyk, Piotr, et al.
Published: (2025)