3 papers
cs.IT2026
Price of metric universality in vector quantization is at most 0.11 bit
Alina Harbuzova, Or Ordentlich, Yury Polyanskiy
Fast computation of a matrix product is a workhorse of modern LLMs. To make their deployment more efficient, a popular approach is that of using a low-precision approxim…
cs.CC2026
Average-Case Reductions for -XOR and Tensor PCA
Guy Bresler, Alina Harbuzova
We study the computational properties of two canonical planted average-case problems -- noisy planted -XOR and Tensor PCA -- by formally unifying them into a family of planted p…
math.ST2025
Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Guy Bresler, Alina Harbuzova
In this work, we show the first average-case reduction transforming the sparse Spiked Covariance Model into the sparse Spiked Wigner Model and as a consequence obtain the first com…