4 papers
Color Coding for the Sherrington-Kirkpatrick Model
Alina Harbuzova, Saba Lepsveridze, Mahbod Majid +1
We give a polynomial-time algorithm for approximating the partition function of mean-field mixed -spin models to arbitrarily high accuracy throughout the second-moment regime. T…
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…
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…
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…