3 papers
cs.LG2026
Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
Nathan White, Krish Singal
Quantization is a fundamental tool used to compress datasets, neural network weights, and memory usage in a range of computational tasks. Many downstream applications of vector qua…
cs.DS2025
Testing noisy low-degree polynomials for sparsity
Yiqiao Bao, Anindya De, Shivam Nadimpalli +2
We consider the problem of testing whether an unknown low-degree polynomial over is sparse versus far from sparse, given access to noisy evaluations of the polyn…
cs.DS2025
Average-Distortion Sketching
Yiqiao Bao, Anubhav Baweja, Nicolas Menand +3
We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwis…