1.8k citations · 18.6k across the 330 of their papers we have counts for
6 papers · 1 filter
The backtracking survey propagation algorithm for solving random K-SAT problems
Raffaele Marino, Giorgio Parisi, Federico Ricci-Tersenghi
Discrete combinatorial optimization has a central role in many scientific disciplines, however, for hard problems we lack linear time algorithms that would allow us to solve very l…
Constraint Optimization and Statistical Mechanics
Giorgio Parisi
In these lectures I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics technique…
On the probabilistic approach to the random satisfiability problem
Giorgio Parisi
In this note I will review some of the recent results that have been obtained in the probabilistic approach to the random satisfiability problem. At the present moment the results…
Some remarks on the survey decimation algorithm for K-satisfiability
Giorgio Parisi
In this note we study the convergence of the survey decimation algorithm. An analytic formula for the reduction of the complexity during the decimation is derived. The limit of the…
On the survey-propagation equations for the random K-satisfiability problem
Giorgio Parisi
In this note we study the existence of a solution to the survey-propagation equations for the random K-satisfiability problem for a given instance. We conjecture that when the numb…
On local equilibrium equations for clustering states
Giorgio Parisi
In this note we show that local equilibrium equations (the generalization of the TAP equations or of the belief propagation equations) do have solutions in the colorable phase of t…