The closest vector problem and the zero-temperature p-spin landscape for lossy compression

Alfredo Braunstein, Louise Budzynski, Stefano Crotti +1

We consider a high-dimensional random constrained optimization problem in which a set of binary variables is subjected to a linear system of equations. The cost function is a simpl…