3 papers
cs.DS2026
Improved Time-Space Tradeoffs for 3SUM-Indexing
Itai Dinur, Alexander Golovnev
3SUM-Indexing is a preprocessing variant of the 3SUM problem that has recently received a lot of attention. The best known time-space tradeoff for the problem is (u…
cs.CC2026
Linear Space Streaming Lower Bounds for Approximating CSPs
Chi-Ning Chou, Alexander Golovnev, Madhu Sudan +2
We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on variables taking values in $\{0…
cs.DS2024
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…