Journal article · 2007 · Open access

Landscape analysis of constraint satisfaction problems

Florent Krząkała, Jorge Kurchan

Physical Review E, 76(2), 021122 · Published 27 August 2007 · DOI 10.1103/physreve.76.021122

Open PDFView at the publisherCite this paper

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

YearCitationsShare of the best year
201722
201855
20191515
202033
20211212
202233
20231010
202466
202588
202644

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

All highly cited Computer Science papers

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.