5 papers · 1 filter
A Matrix Factorization Approach in Turnstile Streaming
Jan Bulanek, Ravi Kumar, Raghu Meka +2
We define the -point query problem in data streams. Given a fixed matrix , the goal is to maintain a vector under turnstile updates and answer each query with an esti…
Optimal Sparsifiers for Abelian Cayley Graphs
Arpon Basu, Pravesh K. Kothari, Raghu Meka +1
We prove that for every Cayley graph over any finite abelian group , there is a weighted Cayley graph with generators that is a spectral sparsifier f…
The Grothendieck Constant is Less Than
Alan Li, Rahul Saha, Anton Xue +4
We prove that the Grothendieck constant . This improves on the work of Braverman, Makarychev, Makarychev, and Naor (2011), who proved…
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1
In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…