DOI: 10.1145/1255443.1255445. A new look at survey propagation and its generalizations

A new look at survey propagation and its generalizations

10.1145/1255443.1255445

Crossref journal-article

Association for Computing Machinery (ACM)

Journal of the ACM (320)

Abstract

This article provides a new conceptual perspective on survey propagation , which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random k -SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number ρ ∈ [0, 1]. We then show that applying belief propagation---a well-known “message-passing” technique for estimating marginal probabilities---to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (ρ = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (ρ = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate cores as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for ρ = 1. Our experimental results for k = 3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for ρ < 1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with ρ > 0 can be viewed as a “smoothed” version of the uniform distribution over satisfying assignments (ρ = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of k -SAT problems.

Bibliography

Maneva, E., Mossel, E., & Wainwright, M. J. (2007). A new look at survey propagation and its generalizations. Journal of the ACM, 54(4), 17.

Authors 3

Elitza Maneva (first)
Elchanan Mossel (additional)
Martin J. Wainwright (additional)

References 49 Referenced 53

Achiloptas , D. , and Peres , Y . 2003. The threshold for random k-SAT is 2k2log 2−o(k) . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 223--231. 10.1145/780542.780577 Achiloptas, D., and Peres, Y. 2003. The threshold for random k-SAT is 2k2log 2−o(k). In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 223--231. 10.1145/780542.780577 / Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press by Achiloptas D.
Achlioptas , D. , and Ricci-Tersenghi , F . 2006. On the solution-space geometry of random constraint satisfaction problems . In Proceedings of the Symposium on Theory of Computing. ACM , New York, 130--139. 10.1145/1132516.1132537 Achlioptas, D., and Ricci-Tersenghi, F. 2006. On the solution-space geometry of random constraint satisfaction problems. In Proceedings of the Symposium on Theory of Computing. ACM, New York, 130--139. 10.1145/1132516.1132537 / Proceedings of the Symposium on Theory of Computing. ACM by Achlioptas D.
Aurell , E. , Gordon , U. , and Kirkpatrick , S . 2004. Comparing beliefs, surveys, and random walks . In Proceedings of NIPS. MIT Press , Cambridge, MA. Aurell, E., Gordon, U., and Kirkpatrick, S. 2004. Comparing beliefs, surveys, and random walks. In Proceedings of NIPS. MIT Press, Cambridge, MA. / Proceedings of NIPS. MIT Press by Aurell E.
Berger , N. , Kenyon , C. , Mossel , E. , and Peres , Y. 2005 . Glauber dynamics on trees and hyperbolic graphs . Probab. Theory Relat. Fields , 131 ( 3 ): 311 -- 340 . (Extended abstract by Kenyon, Mossel and Peres appeared in Proceedings of FOCS.) Berger, N., Kenyon, C., Mossel, E., and Peres, Y. 2005. Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields, 131(3):311--340. (Extended abstract by Kenyon, Mossel and Peres appeared in Proceedings of FOCS.) (10.1007/s00440-004-0369-4) / Probab. Theory Relat. Fields / Glauber dynamics on trees and hyperbolic graphs by Berger N. (2005)
Braunstein A. Mézard M. Weigt M. and Zecchina R. 2003. Constraint satisfaction by survey propagation. Technical report. (Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.) Braunstein A. Mézard M. Weigt M. and Zecchina R. 2003. Constraint satisfaction by survey propagation. Technical report. (Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.)
10.1002/rsa.v27:2
Braunstein , A. , and Zecchina , R. 2004 . Survey propagation as local equilibrium equations . J. Stat. Mech. Theory and Experiments (JSTAT) 7 , 06007 . Braunstein, A., and Zecchina, R. 2004. Survey propagation as local equilibrium equations. J. Stat. Mech. Theory and Experiments (JSTAT) 7, 06007. (10.1088/1742-5468/2004/06/P06007) / J. Stat. Mech. Theory and Experiments (JSTAT) / Survey propagation as local equilibrium equations by Braunstein A. (2004)
Chvatal , V. , and Reed , B . 1992. Mick gets some (the odds are on his side) . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 620--627. Chvatal, V., and Reed, B. 1992. Mick gets some (the odds are on his side). In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 620--627. / Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press by Chvatal V.
Ciliberti S. Mézard M. and Zecchina R. 2005. Message-passing algorithms for non-linear nodes and data compression. Technical report November 2005. arXiv:cond-mat/0508723. Ciliberti S. Mézard M. and Zecchina R. 2005. Message-passing algorithms for non-linear nodes and data compression. Technical report November 2005. arXiv:cond-mat/0508723.
Cook , S. 1971 . The complexity of theorem-proving procedures . In Proceedings of the Symposium on Theory of Computing. ACM , New York, 151--158. 10.1145/800157.805047 Cook, S. 1971. The complexity of theorem-proving procedures. In Proceedings of the Symposium on Theory of Computing. ACM, New York, 151--158. 10.1145/800157.805047 / Proceedings of the Symposium on Theory of Computing. ACM by Cook S. (1971)
10.1016/0004-3702(90)90060-D
Coughlan , J. , and Ferreira , S . 2002. Finding deformable shapes using loopy belief propagation . In Proceedings of European Conference on Computer Vision. Springer-Verlag , New York, 453--468. Coughlan, J., and Ferreira, S. 2002. Finding deformable shapes using loopy belief propagation. In Proceedings of European Conference on Computer Vision. Springer-Verlag, New York, 453--468. / Proceedings of European Conference on Computer Vision. Springer-Verlag by Coughlan J.
10.1016/0004-3702(93)90036-B
de la Vega W. F. 1992. On random 2-sat. Unpublished manuscript. de la Vega W. F. 1992. On random 2-sat. Unpublished manuscript.
Dechter , R. 2003. Constraint processing. Morgan-Kaufmann , Palo Alto, CA . Dechter, R. 2003. Constraint processing. Morgan-Kaufmann, Palo Alto, CA. / Constraint processing. Morgan-Kaufmann by Dechter R.
Dubois , O. , Boufkhad , Y. , and Mandler , J . 2000. Typical random 3-sat formulae and the satisfiability threshold . In Proceedings of SODA. ACM , New York, 126--127. Dubois, O., Boufkhad, Y., and Mandler, J. 2000. Typical random 3-sat formulae and the satisfiability threshold. In Proceedings of SODA. ACM, New York, 126--127. / Proceedings of SODA. ACM by Dubois O.
Feige , U. 2002 . Relations between average case complexity and approximation complexity . In Proceedings of Symposium on Theory of Computing. ACM , New York, 534--543. 10.1145/509907.509985 Feige, U. 2002. Relations between average case complexity and approximation complexity. In Proceedings of Symposium on Theory of Computing. ACM, New York, 534--543. 10.1145/509907.509985 / Proceedings of Symposium on Theory of Computing. ACM by Feige U. (2002)
10.1023/A:1026501619075
Friedgut , E. 1999 . Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem . J. Amer. Math. Soc. 12 , 1017 -- 1054 . Friedgut, E. 1999. Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem. J. Amer. Math. Soc. 12, 1017--1054. (10.1090/S0894-0347-99-00305-7) / J. Amer. Math. Soc. / Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem by Friedgut E. (1999)
Gallager , R. G. 1963. Low-density parity check codes . MIT Press , Cambridge, MA . Gallager, R. G. 1963. Low-density parity check codes. MIT Press, Cambridge, MA. / Low-density parity check codes by Gallager R. G.
10.1016/S0166-218X(99)00034-7
Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York. Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York.
Kaporis , A. , Kirousis , L. M. , and Lalas , E. G . 2000. The probabilistic analysis of a greedy satisfiability algorithm . In Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag , Berlin, Germany, 574--585. Kaporis, A., Kirousis, L. M., and Lalas, E. G. 2000. The probabilistic analysis of a greedy satisfiability algorithm. In Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag, Berlin, Germany, 574--585. / Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag by Kaporis A.
10.1109/18.910572
Kumar , V. 1992 . Algorithms for constraint-satisfaction problems: A survey . AI Mag. 13 , 1, 32 -- 44 . Kumar, V. 1992. Algorithms for constraint-satisfaction problems: A survey. AI Mag. 13, 1, 32--44. / AI Mag. / Algorithms for constraint-satisfaction problems: A survey by Kumar V. (1992)
10.1137/0215020
Maneva , E. , Mossel , E. , and Wainwright , M. J . 2005. A new look at survey propagation and its generalizations . In Proceedings of SODA. 1089--1098 . Maneva, E., Mossel, E., and Wainwright, M. J. 2005. A new look at survey propagation and its generalizations. In Proceedings of SODA. 1089--1098. / Proceedings of SODA. 1089--1098 by Maneva E.
Martinelli , F. 1999. Lectures on Glauber dynamics for discrete spin models . In Lectures on probability theory and statistics (Saint-Flour , 1997 ). Lecture Notes in Math., vol. 1717 . Springer-Verlag , Berlin, Germany, 93--191 Martinelli, F. 1999. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997). Lecture Notes in Math., vol. 1717. Springer-Verlag, Berlin, Germany, 93--191 / Lectures on probability theory and statistics (Saint-Flour by Martinelli F. (1997)
Martinian , E. , and Wainwright , M. J . 2006. Low density codes can achieve the Wyner-Ziv and Gelfand-Pinsker bounds . In International Symposium on Information Theory. IEEE Computer Society Press , Los Alamitos, CA. Martinian, E., and Wainwright, M. J. 2006. Low density codes can achieve the Wyner-Ziv and Gelfand-Pinsker bounds. In International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA. / International Symposium on Information Theory. IEEE Computer Society Press by Martinian E.
Mézard , M. , Parisi , G. , and Zecchina , R. 2002 . Analytic and algorithmic solution of random satisfiability problems . Science , 297 , 812 . (Scienceexpress published on-line 27-June-2002; 10.1126/science.1073287). Mézard, M., Parisi, G., and Zecchina, R. 2002. Analytic and algorithmic solution of random satisfiability problems. Science, 297, 812. (Scienceexpress published on-line 27-June-2002; 10.1126/science.1073287). (10.1126/science.1073287) / Science / Analytic and algorithmic solution of random satisfiability problems by Mézard M. (2002)
Mézard , M. , Ricci-Tersenghi , F. , and Zecchina , R. 2003 . Two solutions to diluted p-spin models and XORSAT problems . J. Stat. Phys. 111 , 505 . Mézard, M., Ricci-Tersenghi, F., and Zecchina, R. 2003. Two solutions to diluted p-spin models and XORSAT problems. J. Stat. Phys. 111, 505. (10.1023/A:1022886412117) / J. Stat. Phys. / Two solutions to diluted p-spin models and XORSAT problems by Mézard M. (2003)
Mézard , M. , and Zecchina , R. 2002 . Random k-satisfiability: From an analytic solution to an efficient algorithm . Phys. Rev. E, 66. Mézard, M., and Zecchina, R. 2002. Random k-satisfiability: From an analytic solution to an efficient algorithm. Phys. Rev. E, 66. (10.1103/PhysRevE.66.056126) / Phys. Rev. E, 66. / Random k-satisfiability: From an analytic solution to an efficient algorithm by Mézard M. (2002)
Monasson , R. , and Zecchina , R. 1997 . Statistical mechanics of the random k-satisfiability model . Phys. Rev. E 3 , 1357 -- 1370 . Monasson, R., and Zecchina, R. 1997. Statistical mechanics of the random k-satisfiability model. Phys. Rev. E 3, 1357--1370. (10.1103/PhysRevE.56.1357) / Phys. Rev. E / Statistical mechanics of the random k-satisfiability model by Monasson R. (1997)
Mora , T. , Mézard , M. , and Zecchina , R. 2005 . Clustering of solutions in the random satisfiability problem . Phys. Rev. Lett. 94. Mora, T., Mézard, M., and Zecchina, R. 2005. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94. / Phys. Rev. Lett. 94. / Clustering of solutions in the random satisfiability problem by Mora T. (2005)
Parisi G. 2002. On local equilibrium equations for clustering states. Technical report. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212047. Parisi G. 2002. On local equilibrium equations for clustering states. Technical report. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212047.
Pearl , J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann , Palo Alto, CA . Pearl, J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann, Palo Alto, CA. / Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann by Pearl J.
10.1109/18.910577
Rosenthal , J. , Plotkin , J. , and Franco , J. 1999 . The probability of pure literals . J. Computat. Logic 9 , 501 -- 513 . Rosenthal, J., Plotkin, J., and Franco, J. 1999. The probability of pure literals. J. Computat. Logic 9, 501--513. (10.1093/logcom/9.4.501) / J. Computat. Logic / The probability of pure literals by Rosenthal J. (1999)
Russell , S. , and Norvig , P . 2003 . Artificial Intelligence: A Modern Approach . Prentice-Hall , Englewood Cliffs, NJ , 2 nd edition edition. Russell, S., and Norvig, P. 2003. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 2nd edition edition. / Artificial Intelligence: A Modern Approach by Russell S. (2003)
Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In D. S. Johnson and M. A. Trick editors Cliques coloring and satisfiability: Second DIMACS implementation challenge. (October 11-13 1993) Providence RI. American Mathematical Society. Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In D. S. Johnson and M. A. Trick editors Cliques coloring and satisfiability: Second DIMACS implementation challenge. (October 11-13 1993) Providence RI. American Mathematical Society.
Stanley , R. P. 1997. Enumerative Combinatorics . Vol. 1. Cambridge University Press , Cambridge, UK . Stanley, R. P. 1997. Enumerative Combinatorics. Vol. 1. Cambridge University Press, Cambridge, UK. / Cambridge University Press by Stanley R. P.
Tatikonda , S. , and Jordan , M. I . 2002. Loopy belief propagation and Gibbs measures . In Proceedings of UAI. 493--500 . Tatikonda, S., and Jordan, M. I. 2002. Loopy belief propagation and Gibbs measures. In Proceedings of UAI. 493--500. / Proceedings of UAI. 493--500 by Tatikonda S.
Wainwright M. J. and Jordan M. I. 2003. Graphical models exponential families and variational methods. Technical report UC Berkeley Department of Statitics No. 649. Preprint at URL:http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJorVariational03.ps. Wainwright M. J. and Jordan M. I. 2003. Graphical models exponential families and variational methods. Technical report UC Berkeley Department of Statitics No. 649. Preprint at URL:http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJorVariational03.ps.
Wainwright , M. J. , and Maneva , E . 2005. Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes . In Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press , Los Alamitos, CA, 1493--1497. Wainwright, M. J., and Maneva, E. 2005. Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes. In Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA, 1493--1497. / Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press by Wainwright M. J.
Wang , J. 1997. Average case computational complexity theory . In Complexity Theory Retrospective, L. Hemaspaandra and A. Selman, Eds. Vol. II , Springer-Verlag . 295--328. Wang, J. 1997. Average case computational complexity theory. In Complexity Theory Retrospective, L. Hemaspaandra and A. Selman, Eds. Vol. II, Springer-Verlag. 295--328. / Vol. II by Wang J.
Welling , M. , and Teh , Y . 2001. Belief optimization: A stable alternative to loopy belief propagation . In Proceedings of UAI. 554--561 . Welling, M., and Teh, Y. 2001. Belief optimization: A stable alternative to loopy belief propagation. In Proceedings of UAI. 554--561. / Proceedings of UAI. 554--561 by Welling M.
10.1109/TIT.2005.850085
Yedidia , J. S. , Freeman , W. T. , and Weiss , Y. 2003 . Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York , Chapt. 8 , 236 -- 239 . Yedidia, J. S., Freeman, W. T., and Weiss, Y. 2003. Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York, Chapt. 8, 236--239. / Chapt. / Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York by Yedidia J. S. (2003)
10.1162/08997660260028674

Dates

Type	When
Created	17 years, 11 months ago (Sept. 14, 2007, 9:44 a.m.)
Deposited	2 months ago (June 18, 2025, 4:22 p.m.)
Indexed	2 months ago (June 19, 2025, 12:52 a.m.)
Issued	18 years, 1 month ago (July 1, 2007)
Published	18 years, 1 month ago (July 1, 2007)
Published Online	18 years, 1 month ago (July 1, 2007)
Published Print	18 years, 1 month ago (July 1, 2007)

Funders 0

None

BibTeX

@article{Maneva_2007, title={A new look at survey propagation and its generalizations}, volume={54}, ISSN={1557-735X}, url={http://dx.doi.org/10.1145/1255443.1255445}, DOI={10.1145/1255443.1255445}, number={4}, journal={Journal of the ACM}, publisher={Association for Computing Machinery (ACM)}, author={Maneva, Elitza and Mossel, Elchanan and Wainwright, Martin J.}, year={2007}, month=jul, pages={17} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        6,
        19
      ]
    ],
    "date-time": "2025-06-19T04:52:42Z",
    "timestamp": 1750308762145,
    "version": "3.41.0"
  },
  "reference-count": 49,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "4",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2007,
            7,
            1
          ]
        ],
        "date-time": "2007-07-01T00:00:00Z",
        "timestamp": 1183248000000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        2007,
        7
      ]
    ]
  },
  "abstract": "<jats:p>\n            This article provides a new conceptual perspective on\n            <jats:italic>survey propagation</jats:italic>\n            , which is an iterative algorithm recently introduced by the statistical physics community that is very effective in solving random\n            <jats:italic>k</jats:italic>\n            -SAT problems even with densities close to the satisfiability threshold. We first describe how any SAT formula can be associated with a novel family of Markov random fields (MRFs), parameterized by a real number \u03c1 \u2208 [0, 1]. We then show that applying belief propagation---a well-known \u201cmessage-passing\u201d technique for estimating marginal probabilities---to this family of MRFs recovers a known family of algorithms, ranging from pure survey propagation at one extreme (\u03c1 = 1) to standard belief propagation on the uniform distribution over SAT assignments at the other extreme (\u03c1 = 0). Configurations in these MRFs have a natural interpretation as partial satisfiability assignments, on which a partial order can be defined. We isolate\n            <jats:italic>cores</jats:italic>\n            as minimal elements in this partial ordering, which are also fixed points of survey propagation and the only assignments with positive probability in the MRF for \u03c1 = 1. Our experimental results for\n            <jats:italic>k</jats:italic>\n            = 3 suggest that solutions of random formulas typically do not possess non-trivial cores. This makes it necessary to study the structure of the space of partial assignments for \u03c1 &lt; 1 and investigate the role of assignments that are very close to being cores. To that end, we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any MRF with \u03c1 &gt; 0 can be viewed as a \u201csmoothed\u201d version of the uniform distribution over satisfying assignments (\u03c1 = 0). Finally, we isolate properties of Gibbs sampling and message-passing algorithms that are typical for an ensemble of\n            <jats:italic>k</jats:italic>\n            -SAT problems.\n          </jats:p>",
  "DOI": "10.1145/1255443.1255445",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2007,
        9,
        14
      ]
    ],
    "date-time": "2007-09-14T13:44:55Z",
    "timestamp": 1189777495000
  },
  "page": "17",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 53,
  "title": "A new look at survey propagation and its generalizations",
  "prefix": "10.1145",
  "volume": "54",
  "author": [
    {
      "given": "Elitza",
      "family": "Maneva",
      "sequence": "first",
      "affiliation": [
        {
          "name": "University of California---Berkeley, Berkeley, California"
        }
      ]
    },
    {
      "given": "Elchanan",
      "family": "Mossel",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "University of California---Berkeley, Berkeley, California"
        }
      ]
    },
    {
      "given": "Martin J.",
      "family": "Wainwright",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "University of California---Berkeley, Berkeley, California"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        2007,
        7
      ]
    ]
  },
  "reference": [
    {
      "volume-title": "Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press",
      "author": "Achiloptas D.",
      "key": "e_1_2_1_1_1",
      "unstructured": "Achiloptas , D. , and Peres , Y . 2003. The threshold for random k-SAT is 2k2log 2&minus;o(k) . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 223--231. 10.1145/780542.780577 Achiloptas, D., and Peres, Y. 2003. The threshold for random k-SAT is 2k2log 2&minus;o(k). In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 223--231. 10.1145/780542.780577"
    },
    {
      "volume-title": "Proceedings of the Symposium on Theory of Computing. ACM",
      "author": "Achlioptas D.",
      "key": "e_1_2_1_2_1",
      "unstructured": "Achlioptas , D. , and Ricci-Tersenghi , F . 2006. On the solution-space geometry of random constraint satisfaction problems . In Proceedings of the Symposium on Theory of Computing. ACM , New York, 130--139. 10.1145/1132516.1132537 Achlioptas, D., and Ricci-Tersenghi, F. 2006. On the solution-space geometry of random constraint satisfaction problems. In Proceedings of the Symposium on Theory of Computing. ACM, New York, 130--139. 10.1145/1132516.1132537"
    },
    {
      "volume-title": "Proceedings of NIPS. MIT Press",
      "author": "Aurell E.",
      "key": "e_1_2_1_3_1",
      "unstructured": "Aurell , E. , Gordon , U. , and Kirkpatrick , S . 2004. Comparing beliefs, surveys, and random walks . In Proceedings of NIPS. MIT Press , Cambridge, MA. Aurell, E., Gordon, U., and Kirkpatrick, S. 2004. Comparing beliefs, surveys, and random walks. In Proceedings of NIPS. MIT Press, Cambridge, MA."
    },
    {
      "issue": "3",
      "key": "e_1_2_1_4_1",
      "doi-asserted-by": "crossref",
      "first-page": "311",
      "DOI": "10.1007/s00440-004-0369-4",
      "article-title": "Glauber dynamics on trees and hyperbolic graphs",
      "volume": "131",
      "author": "Berger N.",
      "year": "2005",
      "unstructured": "Berger , N. , Kenyon , C. , Mossel , E. , and Peres , Y. 2005 . Glauber dynamics on trees and hyperbolic graphs . Probab. Theory Relat. Fields , 131 ( 3 ): 311 -- 340 . (Extended abstract by Kenyon, Mossel and Peres appeared in Proceedings of FOCS.) Berger, N., Kenyon, C., Mossel, E., and Peres, Y. 2005. Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Relat. Fields, 131(3):311--340. (Extended abstract by Kenyon, Mossel and Peres appeared in Proceedings of FOCS.)",
      "journal-title": "Probab. Theory Relat. Fields"
    },
    {
      "key": "e_1_2_1_5_1",
      "unstructured": "Braunstein A. M\u00e9zard M. Weigt M. and Zecchina R. 2003. Constraint satisfaction by survey propagation. Technical report. (Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.)  Braunstein A. M\u00e9zard M. Weigt M. and Zecchina R. 2003. Constraint satisfaction by survey propagation. Technical report. (Preprint at URL:http://lanl.arXiv.org/cond-mat/0212451.)"
    },
    {
      "key": "e_1_2_1_6_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/rsa.v27:2"
    },
    {
      "key": "e_1_2_1_7_1",
      "doi-asserted-by": "crossref",
      "first-page": "06007",
      "DOI": "10.1088/1742-5468/2004/06/P06007",
      "article-title": "Survey propagation as local equilibrium equations",
      "volume": "7",
      "author": "Braunstein A.",
      "year": "2004",
      "unstructured": "Braunstein , A. , and Zecchina , R. 2004 . Survey propagation as local equilibrium equations . J. Stat. Mech. Theory and Experiments (JSTAT) 7 , 06007 . Braunstein, A., and Zecchina, R. 2004. Survey propagation as local equilibrium equations. J. Stat. Mech. Theory and Experiments (JSTAT) 7, 06007.",
      "journal-title": "J. Stat. Mech. Theory and Experiments (JSTAT)"
    },
    {
      "volume-title": "Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press",
      "author": "Chvatal V.",
      "key": "e_1_2_1_8_1",
      "unstructured": "Chvatal , V. , and Reed , B . 1992. Mick gets some (the odds are on his side) . In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 620--627. Chvatal, V., and Reed, B. 1992. Mick gets some (the odds are on his side). In Proceedings of the Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 620--627."
    },
    {
      "key": "e_1_2_1_9_1",
      "unstructured": "Ciliberti S. M\u00e9zard M. and Zecchina R. 2005. Message-passing algorithms for non-linear nodes and data compression. Technical report November 2005. arXiv:cond-mat/0508723.  Ciliberti S. M\u00e9zard M. and Zecchina R. 2005. Message-passing algorithms for non-linear nodes and data compression. Technical report November 2005. arXiv:cond-mat/0508723."
    },
    {
      "key": "e_1_2_1_10_1",
      "volume-title": "Proceedings of the Symposium on Theory of Computing. ACM",
      "author": "Cook S.",
      "year": "1971",
      "unstructured": "Cook , S. 1971 . The complexity of theorem-proving procedures . In Proceedings of the Symposium on Theory of Computing. ACM , New York, 151--158. 10.1145/800157.805047 Cook, S. 1971. The complexity of theorem-proving procedures. In Proceedings of the Symposium on Theory of Computing. ACM, New York, 151--158. 10.1145/800157.805047"
    },
    {
      "key": "e_1_2_1_11_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0004-3702(90)90060-D"
    },
    {
      "volume-title": "Proceedings of European Conference on Computer Vision. Springer-Verlag",
      "author": "Coughlan J.",
      "key": "e_1_2_1_12_1",
      "unstructured": "Coughlan , J. , and Ferreira , S . 2002. Finding deformable shapes using loopy belief propagation . In Proceedings of European Conference on Computer Vision. Springer-Verlag , New York, 453--468. Coughlan, J., and Ferreira, S. 2002. Finding deformable shapes using loopy belief propagation. In Proceedings of European Conference on Computer Vision. Springer-Verlag, New York, 453--468."
    },
    {
      "key": "e_1_2_1_13_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0004-3702(93)90036-B"
    },
    {
      "key": "e_1_2_1_14_1",
      "unstructured": "de la Vega W. F. 1992. On random 2-sat. Unpublished manuscript.  de la Vega W. F. 1992. On random 2-sat. Unpublished manuscript."
    },
    {
      "volume-title": "Constraint processing. Morgan-Kaufmann",
      "author": "Dechter R.",
      "key": "e_1_2_1_15_1",
      "unstructured": "Dechter , R. 2003. Constraint processing. Morgan-Kaufmann , Palo Alto, CA . Dechter, R. 2003. Constraint processing. Morgan-Kaufmann, Palo Alto, CA."
    },
    {
      "volume-title": "Proceedings of SODA. ACM",
      "author": "Dubois O.",
      "key": "e_1_2_1_16_1",
      "unstructured": "Dubois , O. , Boufkhad , Y. , and Mandler , J . 2000. Typical random 3-sat formulae and the satisfiability threshold . In Proceedings of SODA. ACM , New York, 126--127. Dubois, O., Boufkhad, Y., and Mandler, J. 2000. Typical random 3-sat formulae and the satisfiability threshold. In Proceedings of SODA. ACM, New York, 126--127."
    },
    {
      "key": "e_1_2_1_17_1",
      "volume-title": "Proceedings of Symposium on Theory of Computing. ACM",
      "author": "Feige U.",
      "year": "2002",
      "unstructured": "Feige , U. 2002 . Relations between average case complexity and approximation complexity . In Proceedings of Symposium on Theory of Computing. ACM , New York, 534--543. 10.1145/509907.509985 Feige, U. 2002. Relations between average case complexity and approximation complexity. In Proceedings of Symposium on Theory of Computing. ACM, New York, 534--543. 10.1145/509907.509985"
    },
    {
      "key": "e_1_2_1_18_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1023/A:1026501619075"
    },
    {
      "key": "e_1_2_1_19_1",
      "doi-asserted-by": "crossref",
      "first-page": "1017",
      "DOI": "10.1090/S0894-0347-99-00305-7",
      "article-title": "Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem",
      "volume": "12",
      "author": "Friedgut E.",
      "year": "1999",
      "unstructured": "Friedgut , E. 1999 . Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem . J. Amer. Math. Soc. 12 , 1017 -- 1054 . Friedgut, E. 1999. Neccesary and sufficient conditions for sharp threhsolds of graph properties and the k-problem. J. Amer. Math. Soc. 12, 1017--1054.",
      "journal-title": "J. Amer. Math. Soc."
    },
    {
      "volume-title": "Low-density parity check codes",
      "author": "Gallager R. G.",
      "key": "e_1_2_1_20_1",
      "unstructured": "Gallager , R. G. 1963. Low-density parity check codes . MIT Press , Cambridge, MA . Gallager, R. G. 1963. Low-density parity check codes. MIT Press, Cambridge, MA."
    },
    {
      "key": "e_1_2_1_21_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0166-218X(99)00034-7"
    },
    {
      "key": "e_1_2_1_22_1",
      "unstructured": "Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York.  Janson S. Luczak T. and Rucinski A. 2000. Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience New York."
    },
    {
      "volume-title": "Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag",
      "author": "Kaporis A.",
      "key": "e_1_2_1_23_1",
      "unstructured": "Kaporis , A. , Kirousis , L. M. , and Lalas , E. G . 2000. The probabilistic analysis of a greedy satisfiability algorithm . In Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag , Berlin, Germany, 574--585. Kaporis, A., Kirousis, L. M., and Lalas, E. G. 2000. The probabilistic analysis of a greedy satisfiability algorithm. In Proceedings of 10th Annual European Symposium on Algorithms. Springer-Verlag, Berlin, Germany, 574--585."
    },
    {
      "key": "e_1_2_1_24_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/18.910572"
    },
    {
      "key": "e_1_2_1_25_1",
      "first-page": "32",
      "article-title": "Algorithms for constraint-satisfaction problems: A survey",
      "volume": "13",
      "author": "Kumar V.",
      "year": "1992",
      "unstructured": "Kumar , V. 1992 . Algorithms for constraint-satisfaction problems: A survey . AI Mag. 13 , 1, 32 -- 44 . Kumar, V. 1992. Algorithms for constraint-satisfaction problems: A survey. AI Mag. 13, 1, 32--44.",
      "journal-title": "AI Mag."
    },
    {
      "key": "e_1_2_1_26_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0215020"
    },
    {
      "volume-title": "Proceedings of SODA. 1089--1098",
      "author": "Maneva E.",
      "key": "e_1_2_1_27_1",
      "unstructured": "Maneva , E. , Mossel , E. , and Wainwright , M. J . 2005. A new look at survey propagation and its generalizations . In Proceedings of SODA. 1089--1098 . Maneva, E., Mossel, E., and Wainwright, M. J. 2005. A new look at survey propagation and its generalizations. In Proceedings of SODA. 1089--1098."
    },
    {
      "key": "e_1_2_1_28_1",
      "volume-title": "Lectures on probability theory and statistics (Saint-Flour",
      "author": "Martinelli F.",
      "year": "1997",
      "unstructured": "Martinelli , F. 1999. Lectures on Glauber dynamics for discrete spin models . In Lectures on probability theory and statistics (Saint-Flour , 1997 ). Lecture Notes in Math., vol. 1717 . Springer-Verlag , Berlin, Germany, 93--191 Martinelli, F. 1999. Lectures on Glauber dynamics for discrete spin models. In Lectures on probability theory and statistics (Saint-Flour, 1997). Lecture Notes in Math., vol. 1717. Springer-Verlag, Berlin, Germany, 93--191"
    },
    {
      "volume-title": "International Symposium on Information Theory. IEEE Computer Society Press",
      "author": "Martinian E.",
      "key": "e_1_2_1_29_1",
      "unstructured": "Martinian , E. , and Wainwright , M. J . 2006. Low density codes can achieve the Wyner-Ziv and Gelfand-Pinsker bounds . In International Symposium on Information Theory. IEEE Computer Society Press , Los Alamitos, CA. Martinian, E., and Wainwright, M. J. 2006. Low density codes can achieve the Wyner-Ziv and Gelfand-Pinsker bounds. In International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA."
    },
    {
      "key": "e_1_2_1_30_1",
      "doi-asserted-by": "crossref",
      "first-page": "812",
      "DOI": "10.1126/science.1073287",
      "article-title": "Analytic and algorithmic solution of random satisfiability problems",
      "volume": "297",
      "author": "M\u00e9zard M.",
      "year": "2002",
      "unstructured": "M\u00e9zard , M. , Parisi , G. , and Zecchina , R. 2002 . Analytic and algorithmic solution of random satisfiability problems . Science , 297 , 812 . (Scienceexpress published on-line 27-June-2002; 10.1126/science.1073287). M\u00e9zard, M., Parisi, G., and Zecchina, R. 2002. Analytic and algorithmic solution of random satisfiability problems. Science, 297, 812. (Scienceexpress published on-line 27-June-2002; 10.1126/science.1073287).",
      "journal-title": "Science"
    },
    {
      "key": "e_1_2_1_31_1",
      "doi-asserted-by": "crossref",
      "first-page": "505",
      "DOI": "10.1023/A:1022886412117",
      "article-title": "Two solutions to diluted p-spin models and XORSAT problems",
      "volume": "111",
      "author": "M\u00e9zard M.",
      "year": "2003",
      "unstructured": "M\u00e9zard , M. , Ricci-Tersenghi , F. , and Zecchina , R. 2003 . Two solutions to diluted p-spin models and XORSAT problems . J. Stat. Phys. 111 , 505 . M\u00e9zard, M., Ricci-Tersenghi, F., and Zecchina, R. 2003. Two solutions to diluted p-spin models and XORSAT problems. J. Stat. Phys. 111, 505.",
      "journal-title": "J. Stat. Phys."
    },
    {
      "key": "e_1_2_1_32_1",
      "doi-asserted-by": "crossref",
      "DOI": "10.1103/PhysRevE.66.056126",
      "article-title": "Random k-satisfiability: From an analytic solution to an efficient algorithm",
      "author": "M\u00e9zard M.",
      "year": "2002",
      "unstructured": "M\u00e9zard , M. , and Zecchina , R. 2002 . Random k-satisfiability: From an analytic solution to an efficient algorithm . Phys. Rev. E, 66. M\u00e9zard, M., and Zecchina, R. 2002. Random k-satisfiability: From an analytic solution to an efficient algorithm. Phys. Rev. E, 66.",
      "journal-title": "Phys. Rev. E, 66."
    },
    {
      "key": "e_1_2_1_33_1",
      "doi-asserted-by": "crossref",
      "first-page": "1357",
      "DOI": "10.1103/PhysRevE.56.1357",
      "article-title": "Statistical mechanics of the random k-satisfiability model",
      "volume": "3",
      "author": "Monasson R.",
      "year": "1997",
      "unstructured": "Monasson , R. , and Zecchina , R. 1997 . Statistical mechanics of the random k-satisfiability model . Phys. Rev. E 3 , 1357 -- 1370 . Monasson, R., and Zecchina, R. 1997. Statistical mechanics of the random k-satisfiability model. Phys. Rev. E 3, 1357--1370.",
      "journal-title": "Phys. Rev. E"
    },
    {
      "key": "e_1_2_1_34_1",
      "article-title": "Clustering of solutions in the random satisfiability problem",
      "author": "Mora T.",
      "year": "2005",
      "unstructured": "Mora , T. , M\u00e9zard , M. , and Zecchina , R. 2005 . Clustering of solutions in the random satisfiability problem . Phys. Rev. Lett. 94. Mora, T., M\u00e9zard, M., and Zecchina, R. 2005. Clustering of solutions in the random satisfiability problem. Phys. Rev. Lett. 94.",
      "journal-title": "Phys. Rev. Lett. 94."
    },
    {
      "key": "e_1_2_1_35_1",
      "unstructured": "Parisi G. 2002. On local equilibrium equations for clustering states. Technical report. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212047.  Parisi G. 2002. On local equilibrium equations for clustering states. Technical report. Preprint at URL:http://lanl.arXiv.org/cs.CC/0212047."
    },
    {
      "volume-title": "Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann",
      "author": "Pearl J.",
      "key": "e_1_2_1_36_1",
      "unstructured": "Pearl , J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann , Palo Alto, CA . Pearl, J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan-Kaufmann, Palo Alto, CA."
    },
    {
      "key": "e_1_2_1_37_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/18.910577"
    },
    {
      "key": "e_1_2_1_38_1",
      "doi-asserted-by": "crossref",
      "first-page": "501",
      "DOI": "10.1093/logcom/9.4.501",
      "article-title": "The probability of pure literals",
      "volume": "9",
      "author": "Rosenthal J.",
      "year": "1999",
      "unstructured": "Rosenthal , J. , Plotkin , J. , and Franco , J. 1999 . The probability of pure literals . J. Computat. Logic 9 , 501 -- 513 . Rosenthal, J., Plotkin, J., and Franco, J. 1999. The probability of pure literals. J. Computat. Logic 9, 501--513.",
      "journal-title": "J. Computat. Logic"
    },
    {
      "key": "e_1_2_1_39_1",
      "volume-title": "Artificial Intelligence: A Modern Approach",
      "author": "Russell S.",
      "year": "2003",
      "unstructured": "Russell , S. , and Norvig , P . 2003 . Artificial Intelligence: A Modern Approach . Prentice-Hall , Englewood Cliffs, NJ , 2 nd edition edition. Russell, S., and Norvig, P. 2003. Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs, NJ, 2nd edition edition.",
      "edition": "2"
    },
    {
      "key": "e_1_2_1_40_1",
      "unstructured": "Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In D. S. Johnson and M. A. Trick editors Cliques coloring and satisfiability: Second DIMACS implementation challenge. (October 11-13 1993) Providence RI. American Mathematical Society.  Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In D. S. Johnson and M. A. Trick editors Cliques coloring and satisfiability: Second DIMACS implementation challenge. (October 11-13 1993) Providence RI. American Mathematical Society."
    },
    {
      "volume-title": "Cambridge University Press",
      "author": "Stanley R. P.",
      "key": "e_1_2_1_41_1",
      "unstructured": "Stanley , R. P. 1997. Enumerative Combinatorics . Vol. 1. Cambridge University Press , Cambridge, UK . Stanley, R. P. 1997. Enumerative Combinatorics. Vol. 1. Cambridge University Press, Cambridge, UK."
    },
    {
      "volume-title": "Proceedings of UAI. 493--500",
      "author": "Tatikonda S.",
      "key": "e_1_2_1_42_1",
      "unstructured": "Tatikonda , S. , and Jordan , M. I . 2002. Loopy belief propagation and Gibbs measures . In Proceedings of UAI. 493--500 . Tatikonda, S., and Jordan, M. I. 2002. Loopy belief propagation and Gibbs measures. In Proceedings of UAI. 493--500."
    },
    {
      "key": "e_1_2_1_43_1",
      "unstructured": "Wainwright M. J. and Jordan M. I. 2003. Graphical models exponential families and variational methods. Technical report UC Berkeley Department of Statitics No. 649. Preprint at URL:http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJorVariational03.ps.  Wainwright M. J. and Jordan M. I. 2003. Graphical models exponential families and variational methods. Technical report UC Berkeley Department of Statitics No. 649. Preprint at URL:http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJorVariational03.ps."
    },
    {
      "volume-title": "Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press",
      "author": "Wainwright M. J.",
      "key": "e_1_2_1_44_1",
      "unstructured": "Wainwright , M. J. , and Maneva , E . 2005. Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes . In Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press , Los Alamitos, CA, 1493--1497. Wainwright, M. J., and Maneva, E. 2005. Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes. In Proceedings of IEEE International Symposium on Information Theory. IEEE Computer Society Press, Los Alamitos, CA, 1493--1497."
    },
    {
      "volume-title": "Vol. II",
      "author": "Wang J.",
      "key": "e_1_2_1_45_1",
      "unstructured": "Wang , J. 1997. Average case computational complexity theory . In Complexity Theory Retrospective, L. Hemaspaandra and A. Selman, Eds. Vol. II , Springer-Verlag . 295--328. Wang, J. 1997. Average case computational complexity theory. In Complexity Theory Retrospective, L. Hemaspaandra and A. Selman, Eds. Vol. II, Springer-Verlag. 295--328."
    },
    {
      "volume-title": "Proceedings of UAI. 554--561",
      "author": "Welling M.",
      "key": "e_1_2_1_46_1",
      "unstructured": "Welling , M. , and Teh , Y . 2001. Belief optimization: A stable alternative to loopy belief propagation . In Proceedings of UAI. 554--561 . Welling, M., and Teh, Y. 2001. Belief optimization: A stable alternative to loopy belief propagation. In Proceedings of UAI. 554--561."
    },
    {
      "key": "e_1_2_1_47_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1109/TIT.2005.850085"
    },
    {
      "key": "e_1_2_1_48_1",
      "first-page": "236",
      "article-title": "Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York",
      "volume": "8",
      "author": "Yedidia J. S.",
      "year": "2003",
      "unstructured": "Yedidia , J. S. , Freeman , W. T. , and Weiss , Y. 2003 . Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York , Chapt. 8 , 236 -- 239 . Yedidia, J. S., Freeman, W. T., and Weiss, Y. 2003. Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium, Science and Technology books, New York, Chapt. 8, 236--239.",
      "journal-title": "Chapt."
    },
    {
      "key": "e_1_2_1_49_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1162/08997660260028674"
    }
  ],
  "container-title": "Journal of the ACM",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/1255443.1255445",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/1255443.1255445",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T20:22:28Z",
    "timestamp": 1750278148000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/1255443.1255445"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2007,
        7
      ]
    ]
  },
  "references-count": 49,
  "journal-issue": {
    "issue": "4",
    "published-print": {
      "date-parts": [
        [
          2007,
          7
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/1255443.1255445"
  ],
  "URL": "http://dx.doi.org/10.1145/1255443.1255445",
  "relation": {},
  "ISSN": [
    "0004-5411",
    "1557-735X"
  ],
  "subject": [],
  "container-title-short": "J. ACM",
  "published": {
    "date-parts": [
      [
        2007,
        7
      ]
    ]
  },
  "assertion": [
    {
      "value": "2007-07-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}