Disordered systems insights on computational hardness
D Gamarnik, C Moore… - Journal of Statistical …, 2022 - iopscience.iop.org
In this review article we discuss connections between the physics of disordered systems,
phase transitions in inference problems, and computational hardness. We introduce two …
phase transitions in inference problems, and computational hardness. We introduce two …
Tight lipschitz hardness for optimizing mean field spin glasses
We study the problem of algorithmically optimizing the Hamiltonian HN H_N of a spherical or
Ising mixed pp‐spin glass. The maximum asymptotic value OPT OPT of HN/N H_N/N is …
Ising mixed pp‐spin glass. The maximum asymptotic value OPT OPT of HN/N H_N/N is …
Low-degree hardness of random optimization problems
D Gamarnik, A Jagannath… - 2020 IEEE 61st Annual …, 2020 - ieeexplore.ieee.org
We consider the problem of finding nearly optimal solutions of optimization problems with
random objective functions. Such problems arise widely in the theory of random graphs …
random objective functions. Such problems arise widely in the theory of random graphs …
Following the ground states of full‐RSB spherical spin glasses
E Subag - Communications on Pure and Applied Mathematics, 2021 - Wiley Online Library
We focus on spherical spin glasses whose Parisi distribution has support of the form [0, q].
For such models we construct paths from the origin to the sphere that consistently remain …
For such models we construct paths from the origin to the sphere that consistently remain …
A Short Review on Novel Approaches for Maximum Clique Problem: from Classical algorithms to Graph Neural Networks and Quantum algorithms
This manuscript provides a comprehensive review of the Maximum Clique Problem, a
computational problem that involves finding subsets of vertices in a graph that are all …
computational problem that involves finding subsets of vertices in a graph that are all …
Rethinking Mean-Field Glassy Dynamics and Its Relation with the Energy Landscape: The Surprising Case of the Spherical Mixed -Spin Model
The spherical p-spin model is a fundamental model in statistical mechanics of a disordered
system with a random first-order transition. The dynamics of this model is interesting both for …
system with a random first-order transition. The dynamics of this model is interesting both for …
Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics
We consider the problem of finding nearly optimal solutions of optimization problems with
random objective functions. Such problems arise widely in the theory of random graphs …
random objective functions. Such problems arise widely in the theory of random graphs …
Crisanti–Sommers formula and simultaneous symmetry breaking in multi-species spherical spin glasses
There is a rich history of expressing the limiting free energy of mean-field spin glasses as a
variational formula over probability measures on [0, 1], where the measure represents the …
variational formula over probability measures on [0, 1], where the measure represents the …
The high-dimensional landscape paradigm: Spin-glasses, and beyond
V Ros, YV Fyodorov - Spin Glass Theory and Far Beyond: Replica …, 2023 - World Scientific
In this chapter we review recent developments on the characterization of random
landscapes in high dimension. We focus in particular on the problem of characterizing the …
landscapes in high dimension. We focus in particular on the problem of characterizing the …
The high-d landscapes paradigm: spin-glasses, and beyond
V Ros, YV Fyodorov - arXiv preprint arXiv:2209.07975, 2022 - arxiv.org
We review recent developments on the characterization of random landscapes in high-
dimension. We focus in particular on the problem of characterizing the landscape topology …
dimension. We focus in particular on the problem of characterizing the landscape topology …