Alexander Golovnev

collaborators

3 papers

cs.DS2026

Online Orthogonal Vectors Revisited

Karthik Gajulapalli, Alexander Golovnev, Samuel King +1

We prove new upper and lower bounds for the Online Orthogonal Vectors Problem ( $OnlineOV_{n, d}$ ). In this problem, a preprocessing algorithm receives $n$ vectors $x_1,\ldo…

cs.DS2025

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 $n \times n$ matrices $A, B$ when their product $A B$ is promised to have at mo…

math.MG2025

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…