Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

Luca Dall’Asta, Abolfazl Ramezanpour, Riccardo Zecchina

Type: Article

Publication Date: 2008-03-17

Citations: 70

DOI: https://doi.org/10.1103/physreve.77.031118

View Publication

Locations

Physical Review E - View
arXiv (Cornell University) - View
PubMed - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Biased landscapes for random constraint satisfaction problems	2019	Louise Budzynski Federico Ricci‐Tersenghi Guilhem Semerjian
+ PDF Chat	Landscape analysis of constraint satisfaction problems	2007	Florent Krząkała Jorge Kurchan
+	Statistical Physics of Hard Optimization Problems	2008	Lenka Zdeborová
+ PDF Chat	Local entropy as a measure for sampling solutions in constraint satisfaction problems	2016	Carlo Baldassi Alessandro Ingrosso Carlo Lucibello Luca Saglietti Riccardo Zecchina
+ PDF Chat	Phase transitions and computational difficulty in random constraint satisfaction problems	2008	Florent Krząkała Lenka Zdeborová
+ PDF Chat	Hiding Quiet Solutions in Random Constraint Satisfaction Problems	2009	Florent Krząkała Lenka Zdeborová
+ PDF Chat	Gibbs states and the set of solutions of random constraint satisfaction problems	2007	Florent Krząkała Andrea Montanari Federico Ricci‐Tersenghi Guilhem Semerjian Lenka Zdeborová
+	Aspects of Statistical Physics in Computational Complexity	2014	Stefano Gogioso
+ PDF Chat	CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS	2010	Haijun Zhou
+ PDF Chat	Statistical physics of hard optimization problems	2009	Lenka Zdeborová
+	borealis - A generalized global update algorithm for Boolean optimization problems	2016	Zheng Zhu Chao Fang Helmut G. Katzgraber
+	Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold	2023	Angelo Giorgio Cavaliere Federico Ricci‐Tersenghi
+ PDF Chat	Landscape of Solutions in Constraint Satisfaction Problems	2005	Marc Mézard Matteo Palassini Olivier Rivoire
+ PDF Chat	Reweighted Belief Propagation and Quiet Planting for Random K-SAT	2014	Florent Krząkała Marc Mézard Lenka Zdeborová
+ PDF Chat	The solution space structure of random constraint satisfaction problems with growing domains	2015	Wei Xu Pan Zhang Tian Liu Fuzhou Gong
+ PDF Chat	Exhaustive enumeration unveils clustering and freezing in the random 3-satisfiability problem	2008	John Ardelius Lenka Zdeborová
+	Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses	2022	Chris Jones Kunal Marwaha Juspreet Singh Sandhu Jonathan Shi
+ PDF Chat	Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses	2022	Chris Jones Kunal Marwaha Juspreet Singh Sandhu Jonathan Shi
+	The cavity method: from exact solutions to algorithms	2022	Alfredo Braunstein Guilhem Semerjian
+ PDF Chat	The Cavity Method: From Exact Solutions to Algorithms	2023	Alfredo Braunstein Guilhem Semerjian

Works That Cite This (53)

Action	Title	Year	Authors
+ PDF Chat	Clustering of neural code words revealed by a first-order phase transition	2016	Haiping Huang Taro Toyoizumi
+	Random Walks and Rapid Mixing	2011	Cristopher Moore Stephan Mertens
+ PDF Chat	Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula	2010	Haijun Zhou
+ PDF Chat	Locked Constraint Satisfaction Problems	2008	Lenka Zdeborová Marc Mézard
+ PDF Chat	Exact satisfiability threshold for<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-satisfiability problems on a Bethe lattice	2015	Supriya Krishnamurthy M. Leone Sumedha
+ PDF Chat	The Network Source Location Problem: Ground State Energy, Entropy and Effects of Freezing	2014	Haiping Huang Jack Raymond K. Y. Michael Wong
+	Satisfiability Thresholds for Regular Occupation Problems	2018	Matija Pasch Κωνσταντίνος Παναγιώτου
+ PDF Chat	Local entropy as a measure for sampling solutions in constraint satisfaction problems	2016	Carlo Baldassi Alessandro Ingrosso Carlo Lucibello Luca Saglietti Riccardo Zecchina
+ PDF Chat	The large deviations of the whitening process in random constraint satisfaction problems	2016	Alfredo Braunstein Luca Dall’Asta Guilhem Semerjian Lenka Zdeborová
+ PDF Chat	The Asymptotics of the Clustering Transition for Random Constraint Satisfaction Problems	2020	Louise Budzynski Guilhem Semerjian

Works Cited by This (19)

Action	Title	Year	Authors
+	None	2003	Marc Mézard Federico Ricci‐Tersenghi Riccardo Zecchina
+ PDF Chat	Sharp thresholds of graph properties, and the $k$-sat problem	1999	Ehud Friedgut appendix by Jean Bourgain
+ PDF Chat	Coloring Random Graphs	2002	Roberto Mulet Andrea Pagnani Martin Weigt Riccardo Zecchina
+ PDF Chat	Bicolouring random hypergraphs	2003	Tommaso Castellani Vincenzo Napolano Federico Ricci‐Tersenghi Riccardo Zecchina
+ PDF Chat	Landscape analysis of constraint satisfaction problems	2007	Florent Krząkała Jorge Kurchan
+ PDF Chat	On the nature of the low-temperature phase in discontinuous mean-field spin glasses	2003	Andrea Montanari Federico Ricci‐Tersenghi
+ PDF Chat	Statistical Mechanics of Systems with Heterogeneous Agents: Minority Games	2000	Damien Challet Matteo Marsili Riccardo Zecchina
+ PDF Chat	The Bethe lattice spin glass revisited	2001	Marc Mézard Giorgio Parisi
+ PDF Chat	Efficient supervised learning in networks with binary synapses	2007	Carlo Baldassi Alfredo Braunstein Nicolas Brunel Riccardo Zecchina
+ PDF Chat	Statistical Mechanics of Combinatorial Auctions	2006	Tobias Galla Michele Leone Matteo Marsili Mauro Sellitto Martin Weigt Riccardo Zecchina