4 papers
Output-Sparse Matrix Multiplication Using Compressed Sensing
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1
We give two algorithms for output-sparse matrix multiplication (OSMM), the problem of multiplying two matrices when their product is promised to have at mo…
Graph Inference with Effective Resistance Queries
Huck Bennett, Mitchell Black, Amir Nayyeri +1
The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruct…
Difficulties Constructing Lattices with Exponential Kissing Number from Codes
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-we…
Matrix Multiplication Verification Using Coding Theory
Huck Bennett, Karthik Gajulapalli, Alexander Golovnev +1
We study the Matrix Multiplication Verification Problem (MMV) where the goal is, given three matrices , , and as input, to decide whether . A classic…