Karthik Gajulapalli

activity

20232026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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…

cs.DS2023

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 $n \times n$ matrices $A$ , $B$ , and $C$ as input, to decide whether $A B = C$ . A classic…