Source author record

Guilhem Semerjian

Guilhem Semerjian appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

15works
14topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

Aligning random graphs with a sub-tree similarity message-passing algorithm

The problem of aligning Erdös-Rényi random graphs is a noisy, average-case version of the graph isomorphism problem, in which a pair of correlated random graphs is observed through a random permutation of their vertices. We study a polynomial time message-passing algorithm devised to solve the inference problem of partially recovering the hidden permutation, in the sparse regime with constant average degrees. We perform extensive numerical simulations to determine the range of parameters in which this algorithm achieves partial recovery. We also introduce a generalized ensemble of correlated random graphs with prescribed degree distributions, and extend the algorithm to this case.

preprint2020arXiv

Recovery thresholds in the sparse planted matching problem

We consider the statistical inference problem of recovering an unknown perfect matching, hidden in a weighted random graph, by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted matching. A recent work has demonstrated the existence of a phase transition, in the large size limit, between a full and a partial recovery phase for a specific form of the weights distribution on fully connected graphs. We generalize and extend this result in two directions: we obtain a criterion for the location of the phase transition for generic weights distributions and possibly sparse graphs, exploiting a technical connection with branching random walk processes, as well as a quantitatively more precise description of the critical regime around the phase transition.

preprint2016arXiv

Network dismantling

We study the network dismantling problem, which consists in determining a minimal set of vertices whose removal leaves the network broken into connected components of sub-extensive size. For a large class of random graphs, this problem is tightly connected to the decycling problem (the removal of vertices leaving the graph acyclic). Exploiting this connection and recent works on epidemic spreading we present precise predictions for the minimal size of a dismantling set in a large random graph with a prescribed (light-tailed) degree distribution. Building on the statistical mechanics perspective we propose a three-stage Min-Sum algorithm for efficiently dismantling networks, including heavy-tailed ones for which the dismantling and decycling problems are not equivalent. We also provide further insights into the dismantling problem concluding that it is an intrinsically collective problem and that optimal dismantling sets cannot be viewed as a collection of individually well performing nodes.

preprint2015arXiv

Thermal, quantum and simulated quantum annealing: analytical comparisons for simple models

We study various annealing dynamics, both classical and quantum, for simple mean-field models and explain how to describe their behavior in the thermodynamic limit in terms of differential equations. In particular we emphasize the differences between quantum annealing (i.e. evolution with Schrödinger equation) and simulated quantum annealing (i.e. annealing of a Quantum Monte Carlo simulation).

preprint2014arXiv

Minimal contagious sets in random regular graphs

The bootstrap percolation (or threshold model) is a dynamic process modelling the propagation of an epidemic on a graph, where inactive vertices become active if their number of active neighbours reach some threshold. We study an optimization problem related to it, namely the determination of the minimal number of active sites in an initial configuration that leads to the activation of the whole graph under this dynamics, with and without a constraint on the time needed for the complete activation. This problem encompasses in special cases many extremal characteristics of graphs like their independence, decycling or domination number, and can also be seen as a packing problem of repulsive particles. We use the cavity method (including the effects of replica symmetry breaking), an heuristic technique of statistical mechanics many predictions of which have been confirmed rigorously in the recent years. We have obtained in this way several quantitative conjectures on the size of minimal contagious sets in large random regular graphs, the most striking being that 5-regular random graph with a threshold of activation of 3 (resp. 6-regular with threshold 4) have contagious sets containing a fraction 1/6 (resp. 1/4) of the total number of vertices. Equivalently these numbers are the minimal fraction of vertices that have to be removed from a 5-regular (resp. 6-regular) random graph to destroy its 3-core. We also investigated Survey Propagation like algorithmic procedures for solving this optimization problem on single instances of random regular graphs.

preprint2013arXiv

The effect of quantum fluctuations on the coloring of random graphs

We present a study of the coloring problem (antiferromagnetic Potts model) of random regular graphs, submitted to quantum fluctuations induced by a transverse field, using the quantum cavity method and quantum Monte-Carlo simulations. We determine the order of the quantum phase transition encountered at low temperature as a function of the transverse field and discuss the structure of the quantum spin glass phase. In particular, we conclude that the quantum adiabatic algorithm would fail to solve efficiently typical instances of these problems because of avoided level crossings within the quantum spin glass phase, caused by a competition between energetic and entropic effects.

preprint2012arXiv

On quantum mean-field models and their quantum annealing

This paper deals with fully-connected mean-field models of quantum spins with p-body ferromagnetic interactions and a transverse field. For p=2 this corresponds to the quantum Curie-Weiss model (a special case of the Lipkin-Meshkov-Glick model) which exhibits a second-order phase transition, while for p>2 the transition is first order. We provide a refined analytical description both of the static and of the dynamic properties of these models. In particular we obtain analytically the exponential rate of decay of the gap at the first-order transition. We also study the slow annealing from the pure transverse field to the pure ferromagnet (and vice versa) and discuss the effect of the first-order transition and of the spinodal limit of metastability on the residual excitation energy, both for finite and exponentially divergent annealing times. In the quantum computation perspective this quantity would assess the efficiency of the quantum adiabatic procedure as an approximation algorithm.

preprint2012arXiv

The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective

Among various algorithms designed to exploit the specific properties of quantum computers with respect to classical ones, the quantum adiabatic algorithm is a versatile proposition to find the minimal value of an arbitrary cost function (ground state energy). Random optimization problems provide a natural testbed to compare its efficiency with that of classical algorithms. These problems correspond to mean field spin glasses that have been extensively studied in the classical case. This paper reviews recent analytical works that extended these studies to incorporate the effect of quantum fluctuations, and presents also some original results in this direction.

preprint2011arXiv

Lifshitz tails on the Bethe lattice: a combinatorial approach

The density of states of disordered hopping models generically exhibits an essential singularity around the edges of its support, known as a Lifshitz tail. We study this phenomenon on the Bethe lattice, i.e. for the large-size limit of random regular graphs, converging locally to the infinite regular tree, for both diagonal and off-diagonal disorder. The exponential growth of the volume and surface of balls on these lattices is an obstacle for the techniques used to characterize the Lifshitz tails in the finite-dimensional case. We circumvent this difficulty by computing bounds on the moments of the density of states, and by deriving their implications on the behavior of the integrated density of states.

preprint2011arXiv

The quantum Biroli-Mézard model: glass transition and superfluidity in a quantum lattice glass model

We study the quantum version of a lattice model whose classical counterpart captures the physics of structural glasses. We discuss the role of quantum fluctuations in such systems and in particular their interplay with the amorphous order developed in the glass phase. We show that quantum fluctuations might facilitate the formation of the glass at low enough temperature. We also show that the glass transition becomes a first-order transition between a superfluid and an insulating glass at very low temperature, and is therefore accompanied by phase coexistence between superfluid and glassy regions.

preprint2010arXiv

A solvable model of quantum random optimization problems

We study the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. We find a complex low-energy spectrum of the quantum Hamiltonian, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. We expect this complex structure to have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems.

preprint2010arXiv

Analytical approaches to time and length scales in models of glasses

The goal of this chapter is to review recent analytical results about the growth of a (static) correlation length in glassy systems, and the connection that can be made between this length scale and the equilibrium correlation time of its dynamics. The definition of such a length scale is first given in a generic setting, including finite-dimensional models, along with rigorous bounds linking it to the correlation time. We then present some particular cases (finite connectivity mean-field models, and Kac limit of finite dimensional systems) where this length can be actually computed.

preprint2010arXiv

Anderson model on Bethe lattices: density of states, localization properties and isolated eigenvalue

We revisit the Anderson localization problem on Bethe lattices, putting in contact various aspects which have been previously only discussed separately. For the case of connectivity 3 we compute by the cavity method the density of states and the evolution of the mobility edge with disorder. Furthermore, we show that below a certain critical value of the disorder the smallest eigenvalue remains delocalized and separated by all the others (localized) ones by a gap. We also study the evolution of the mobility edge at the center of the band with the connectivity, and discuss the large connectivity limit.

preprint2009arXiv

Exact solution of the Bose-Hubbard model on the Bethe lattice

The exact solution of a quantum Bethe lattice model in the thermodynamic limit amounts to solve a functional self-consistent equation. In this paper we obtain this equation for the Bose-Hubbard model on the Bethe lattice, under two equivalent forms. The first one, based on a coherent state path integral, leads in the large connectivity limit to the mean field treatment of Fisher et al. [Phys. Rev. B {\bf 40}, 546 (1989)] at the leading order, and to the bosonic Dynamical Mean Field Theory as a first correction, as recently derived by Byczuk and Vollhardt [Phys. Rev. B {\bf 77}, 235106 (2008)]. We obtain an alternative form of the equation using the occupation number representation, which can be easily solved with an arbitrary numerical precision, for any finite connectivity. We thus compute the transition line between the superfluid and Mott insulator phases of the model, along with thermodynamic observables and the space and imaginary time dependence of correlation functions. The finite connectivity of the Bethe lattice induces a richer physical content with respect to its infinitely connected counterpart: a notion of distance between sites of the lattice is preserved, and the bosons are still weakly mobile in the Mott insulator phase. The Bethe lattice construction can be viewed as an approximation to the finite dimensional version of the model. We show indeed a quantitatively reasonable agreement between our predictions and the results of Quantum Monte Carlo simulations in two and three dimensions.

preprint2009arXiv

On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

We introduce a version of the cavity method for diluted mean-field spin models that allows the computation of thermodynamic quantities similar to the Franz-Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random constraint satisfaction problems. This allows to develop a theoretical understanding of a class of algorithms for solving constraint satisfaction problems, in which elementary degrees of freedom are sequentially assigned according to the results of a message passing procedure (belief-propagation). We confront this theoretical analysis to the results of extensive numerical simulations.