Journal article · 2007 · Open access
Landscape analysis of constraint satisfaction problems
Physical Review E, 76(2), 021122 · Published 27 August 2007 · DOI 10.1103/physreve.76.021122
In brief
“Landscape analysis of constraint satisfaction problems” is a 2007 journal article by Florent Krząkała and Jorge Kurchan, published in Physical Review E. OpenAlex counts 173 citations as of 22 November 2026, which puts it in the top 8% of works published in 2007 by citations. It is open access: the full text is free to read at arXiv (Cornell University).
- Citations
- 173
- Most cited in
- 2019 (15)
- Field-weighted impact
- 11.65
- References
- 70
- Authors
- 2
Abstract
We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms of an effective energy landscape. Several intriguing geometrical properties of the solution space become in this light familiar in terms of the well-studied ones of rugged (glassy) energy landscapes. A benchmark algorithm naturally suggested by this construction finds solutions in polynomial time up to a point beyond the clustering and in some cases even the thermodynamic transitions. This point has a simple geometric meaning and can be in principle determined with standard statistical mechanical methods, thus pushing the analytic bound up to which problems are guaranteed to be easy. We illustrate this for the graph 3- and 4-coloring problem. For packing problems the present discussion allows to better characterize the J-point, proposed as a systematic definition of random close packing, and to place it in the context of other theories of glasses.
Cite this paper
Formatted from the catalogue record. Check names, capitals and page numbers against the paper before you submit.
APA 7
Krząkała, F., & Kurchan, J. (2007). Landscape analysis of constraint satisfaction problems. Physical Review E, 76(2), 021122. https://doi.org/10.1103/physreve.76.021122
MLA 9
Krząkała, Florent, and Jorge Kurchan. “Landscape analysis of constraint satisfaction problems.” Physical Review E, vol. 76, no. 2, 2007, p. 021122. https://doi.org/10.1103/physreve.76.021122.
Chicago
Krząkała, Florent and Jorge Kurchan. 2007. “Landscape analysis of constraint satisfaction problems.” Physical Review E 76 (2): 021122. https://doi.org/10.1103/physreve.76.021122.
Harvard
Krząkała, F. and Kurchan, J. (2007) ‘Landscape analysis of constraint satisfaction problems’, Physical Review E, 76(2), p. 021122. doi:10.1103/physreve.76.021122.
IEEE
F. Krząkała and J. Kurchan, “Landscape analysis of constraint satisfaction problems,” Physical Review E, vol. 76, no. 2, p. 021122, 2007, doi: 10.1103/physreve.76.021122.
BibTeX
@article{krzakaa2007landscape,
title = {{Landscape analysis of constraint satisfaction problems}},
author = {Krząkała, Florent and Kurchan, Jorge},
journal = {Physical Review E},
year = {2007},
volume = {76},
number = {2},
pages = {021122},
doi = {10.1103/physreve.76.021122},
url = {https://doi.org/10.1103/physreve.76.021122}
}
Download for a reference manager: BibTeX (.bib) · RIS for Zotero, Mendeley and EndNote (.ris)
Citations by year
| Year | Citations | Share of the best year |
|---|---|---|
| 2017 | 2 | |
| 2018 | 5 | |
| 2019 | 15 | |
| 2020 | 3 | |
| 2021 | 12 | |
| 2022 | 3 | |
| 2023 | 10 | |
| 2024 | 6 | |
| 2025 | 8 | |
| 2026 | 4 |
Its field-weighted citation impact is 11.65: it has been cited 11.65 times as often as the average work of the same field, type and year (1.00 is the world average).
Topic and keywords
Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
- constraint satisfaction
- energy landscape
- solution space geometry
- k-SAT
- graph coloring
- sphere packing
- random close packing
- J point
Work with this paper
Most-cited papers in Computer Science
- ImageNet classification with deep convolutional neural networksAlex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton · Communications of the ACM · 2017 · 114,726 citations
- Long Short-Term MemorySepp Hochreiter, Jürgen Schmidhuber · Neural Computation · 1997 · 109,097 citations
- A Mathematical Theory of CommunicationClaude E. Shannon · Bell System Technical Journal · 1948 · 91,736 citations
- Deep learningYann LeCun, Yoshua Bengio, Geoffrey E. Hinton · Nature · 2015 · 90,226 citations
- Faster R-CNN: Towards Real-Time Object Detection with Region Proposal NetworksShaoqing Ren, Kaiming He, Ross Girshick and 1 more · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2016 · 74,143 citations
Questions about this paper
How do I cite this paper in APA style?
Krząkała, F., & Kurchan, J. (2007). Landscape analysis of constraint satisfaction problems. Physical Review E, 76(2), 021122. https://doi.org/10.1103/physreve.76.021122
How many times has this paper been cited?
173 times, according to OpenAlex on 22 November 2026. Google Scholar and Scopus count different sets of sources, so their numbers differ.
Is this paper free to read?
Yes. It is open access at arXiv (Cornell University): sign in and open the PDF from this page.
Who wrote this paper?
Florent Krząkała, Jorge Kurchan.
What is the DOI of this paper?
10.1103/physreve.76.021122, permanently at https://doi.org/10.1103/physreve.76.021122. Sign in and open it from this page.
Bibliographic data from OpenAlex (CC0), last checked 22 November 2026. ResearchGuru does not host this paper; once you are signed in, the links open it at the publisher or the repository that does.