# Séminaire du LPTMS : Louise Budzynski (DISAT)

## The closest vector problem and the spin glass model with external fields for lossy compression

### Louise Budzynski (Department of Applied Science and Technology of Politecnico di Torino)

Hybrid seminar: onsite + zoom.

Zoom link: https://cnrs.zoom.us/j/96894507041?pwd=TVBYWU94UlJ5WUlDSENxZkljSFRvdz09

Meeting ID: 968 9450 7041

Passcode: PwEm1X

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 simple linear cost, measuring the Hamming distance with respect to a reference configuration. Despite its apparent simplicity, this problem exhibits a rich phenomenology.

We show that different situations arise depending on the random ensemble of linear systems. When each variable is involved in at most two linear constraints, we show that the problem can be partially solved analytically, in particular we show that upon convergence, the zero-temperature limit of the cavity equations returns the optimal solution.

We then study the geometrical properties of more general random ensembles. In particular we observe a range in the density of constraints at which the systems enters a glassy phase where the cost function has many minima.

Interestingly, the algorithmic performances are only sensitive to a further phase transition affecting the structure of configuration allowed by the linear constraints.

We also extend our results to variables belonging to GF(q), the Galois Field of order q. We show that increasing the value of q allows to achieve a better optimum, which is confirmed by the Replica Symmetric cavity method predictions.

**Date/Time : ** 15/03/2022 - *11:00 - 12:00*

**Location : ** Grand amphi, bâtiment Pascal n° 530

#### Upcoming seminars

- Séminaire du LPTMS : Martin Robert-de-Saint-Vincent (LPL) - 13 Dec 2022 - 11:00
- Séminaire du LPTMS : Andrei Rotaru (LPTHE) - 10 Jan 2023 - 11:00
- Séminaire du LPTMS : Luca Salasnich (Padova University) - 17 Jan 2023 - 11:00
- Séminaire du LPTMS : Patrick Cheinet (LAC) - 24 Jan 2023 - 11:00
- Séminaire du LPTMS : Igor Bodrenko (Cagliari University) - 31 Jan 2023 - 11:00
- Séminaire du LPTMS : Sanjay Moudgalya (Stanford) - 7 Feb 2023 - 11:00
- Séminaire du LPTMS : Muhittin Mungan (Cologne University) - 14 Feb 2023 - 11:00
- Séminaire du LPTMS : Mathias Rousset (IRMAR) - 7 Mar 2023 - 11:00
- Séminaire du LPTMS : Christopher Lee Baldwin (JQI) - 21 Mar 2023 - 11:00