4 papers
Online Orthogonal Vectors Revisited
Karthik Gajulapalli, Alexander Golovnev, Samuel King +1
We prove new upper and lower bounds for the Online Orthogonal Vectors Problem (). In this problem, a preprocessing algorithm receives vectors $x_1,\ldo…
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…
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…
Hilbert Functions and Low-Degree Randomness Extractors
Alexander Golovnev, Zeyu Guo, Pooya Hatami +2
For , consider the linear space of restrictions of degree- polynomials to . The Hilbert function of , denoted , is the…