From the 1 of 8 linked papers with an AI index.
4 papers · 1 filter
Almost Navigable Graphs
Pratyush Avi, Christopher Musco
The paper introduces γ‑almost navigability, a relaxed graph property for approximate nearest neighbor search that enables construction of sparse, space‑efficient search graphs in n…
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…
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…
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…