# Efficient approximation of branching random walk Gibbs measures

@inproceedings{Ho2021EfficientAO, title={Efficient approximation of branching random walk Gibbs measures}, author={Fu Ho and Pascal Maillard}, year={2021} }

Disordered systems such as spin glasses have been used extensively as models for highdimensional random landscapes and studied from the perspective of optimization algorithms. In a recent paper by L. Addario-Berry and the second author, the continuous random energy model (CREM) was proposed as a simple toy model to study the efficiency of such algorithms. The following question was raised in that paper: what is the threshold βG, at which sampling (approximately) from the Gibbs measure at… Expand

#### Figures from this paper

#### References

SHOWING 1-10 OF 24 REFERENCES

The near-critical Gibbs measure of the branching random walk

- Mathematics
- 2017

Consider the supercritical branching random walk on the real line in the boundary case and the associated Gibbs measure ν(n,β) on the n-th generation, which is also the polymer measure on a… Expand

The algorithmic hardness threshold for continuous random energy models

- Mathematics, Physics
- ArXiv
- 2018

An algorithmic hardness result for finding low-energy states in the so-called CREM, introduced by Bovier and Kurkova in 2004 as an extension of Derrida's generalized random energy model is proved. Expand

On the trajectory of an individual chosen according to supercritical Gibbs measure in the branching random walk

- Mathematics
- Stochastic Processes and their Applications
- 2019

Abstract Consider a branching random walk on the real line. Madaule (2016) showed the renormalized trajectory of an individual selected according to the critical Gibbs measure converges in law to a… Expand

The near-critical scaling window for directed polymers on disordered trees

- Mathematics
- 2012

We study a directed polymer model in a random environment on infinite binary trees. The model is characterized by a phase transition depending on the inverse temperature. We concentrate on the… Expand

Convergence in Law for the Branching Random Walk Seen from Its Tip

- Mathematics
- 2011

Consider a critical branching random walk on the real line. In a recent paper, Aïdékon (2011) developed a powerful method to obtain the convergence in law of its minimum after a log-factor… Expand

Optimization of the Sherrington-Kirkpatrick Hamiltonian

- Computer Science, Mathematics
- 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
- 2019

This work gives an algorithm that, for any ε > 0, outputs a feasible solution whose value is at least (1 – ε) of the optimum, with probability converging to one as the dimension n of the matrix diverges. Expand

Convergence in law of the minimum of a branching random walk

- Mathematics
- 2011

We consider the minimum of a super-critical branching random walk. Addario-Berry and Reed [Ann. Probab. 37 (2009) 1044–1079] proved the tightness of the minimum centered around its mean value. We… Expand

Following the Ground States of
Full‐RSB
Spherical Spin Glasses

- Mathematics, Physics
- 2018

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 which consistently remain close to the… Expand

Derrida's Generalized Random Energy models 2: models with continuous hierarchies

- Mathematics, Physics
- 2004

Abstract This is the second of a series of three papers in which we present a rigorous analysis of Derrida's Generalized Random Energy Models (GREM). Here we study the general case of models with a… Expand

Asymptotic properties and absolute continuity of laws stable by random weighted mean

- Mathematics
- 2001

Abstract We study properties of stable-like laws, which are solutions of the distributional equation Z = d ∑ i=1 N A i Z i , where (N,A1,A2,…) is a given random variable with values in… Expand