4 papers · 1 filter
Almost Navigable Graphs
Pratyush Avi, Christopher Musco
Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (…
An Exact Algorithm for the Unanimous Vote Problem
Feyza Duman Keles, Lisa Hellerstein, Kunal Marwaha +2
Consider independent, biased coins, each with a known probability of heads. Presented with an ordering of these coins, flip (i.e., toss) each coin once, in that order, until we…
Does block size matter in randomized block Krylov low-rank approximation?
Tyler Chen, Ethan N. Epperly, Raphael A. Meyer +2
We study the problem of computing a rank- approximation of a matrix using randomized block Krylov iteration. Prior work has shown that, for block size or , a $(1…
Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen +5
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix given access to matrix-vector product (matvec) queries of the…