DOI: 10.1016/s0166-218x(99)00032-3. Satisfiability threshold for random XOR-CNF formulas

Satisfiability threshold for random XOR-CNF formulas

10.1016/s0166-218x(99)00032-3

Crossref journal-article

Elsevier BV

Discrete Applied Mathematics (78)

Bibliography

Creignou, N., & Daude, H. (1999). Satisfiability threshold for random XOR-CNF formulas. Discrete Applied Mathematics, 96â97, 41â53.

Authors 2

Nadia Creignou (first)
Hervé Daude (additional)

References 18 Referenced 35

10.1016/0020-0190(79)90002-4 / Inform. Processing Lett. / A linear-time algorithm for testing the truth of certain quantified boolean formulas by Aspvall (1979)
B. Bollobás, Random Graphs, Academic Press, New York 1985.
V. Chvátal, B. Reed, Mick gets some (the odds are on his side), in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, IEEE, 1992, pp. 620–627. (10.1109/SFCS.1992.267789)
L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, 1974. (10.1007/978-94-010-2196-8)
S.A. Cook, The complexity of theorem-proving procedures, in: Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. (10.1145/800157.805047)
J.M. Crawford, D. Auton, Experimental results on the crossover point in satisfiability problems, in: Proceedings of the 11th National Conference on Artificial Intelligence, 1993, pp. 21–27.
10.1006/inco.1996.0016 / Inform. Comput. / Complexity of generalized satisfiability counting problems by Creignou (1996)
{'key': '10.1016/S0166-218X(99)00032-3_BIB8', 'first-page': '17', 'article-title': 'On the evolution of random graphs', 'volume': '7', 'author': 'Erdös', 'year': '1960', 'journal-title': 'Publ. Math. Inst. Hungar. Acad. Sci.'} / Publ. Math. Inst. Hungar. Acad. Sci. / On the evolution of random graphs by Erdös (1960)
10.2307/2314805 / Amer. Math. Mon. / Matrices over a finite field by Fisher (1966)
10.1006/jagm.1996.0016 / J. Algorithms / Analysis of two simple heuristics on a random instance of k-SAT by Frieze (1996)
I.P. Gent, T. Walsh, The SAT phase transition, in: Proceedings of the 11th European Conference on Artificial Intelligence, 1994, pp. 105–109.
A. Goerdt, A threshold for unsatisfiability, in: L. Havel, V. Koubek (Eds.), Mathematical Foundations of Computer Science, Springer, Berlin, 1992, pp. 264–274. (10.1007/3-540-55808-X_25)
A. Kamatah, R. Motwani, K. Palem, P. Spirakis, Tail bounds for occupancy and the satisfiability threshold conjecture, in: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994, pp. 592–603. (10.1109/SFCS.1994.365732)
10.1137/1112005 / Theory Probab. Appl. / On the limit distribution of the number of solutions of a random system of linear equations in the class of boolean functions by Kovalenko (1967)
D. Mitchell, B. Selman, H. Levesque, Hard and easy distributions of SAT problems, in: Proceedings of the 10th National Conference on Artificial Intelligence, 1992, pp. 459–465.
A. Rényi, Calcul des Probabilités, Dunod, Paris, 1966.
T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings 10th STOC, San Diego (CA, USA), Association for Computing Machinery, 1978, pp. 216–226. (10.1145/800133.804350)
{'key': '10.1016/S0166-218X(99)00032-3_BIB18', 'first-page': '283', 'article-title': "Etude statistique de l'existence de solutions de problèmes SAT, et application aux systèmes-experts", 'volume': '7', 'author': 'Simon', 'year': '1986', 'journal-title': "Compte Rendus de l'Académie des Sciences de Paris, tome 302, Sér. I"} / Compte Rendus de l'Académie des Sciences de Paris, tome 302, Sér. I / Etude statistique de l'existence de solutions de problèmes SAT, et application aux systèmes-experts by Simon (1986)

Dates

Type	When
Created	23 years ago (July 25, 2002, 1:35 p.m.)
Deposited	6 years, 3 months ago (April 24, 2019, 2:54 p.m.)
Indexed	1 month, 2 weeks ago (July 7, 2025, 4:24 a.m.)
Issued	25 years, 10 months ago (Oct. 1, 1999)
Published	25 years, 10 months ago (Oct. 1, 1999)
Published Print	25 years, 10 months ago (Oct. 1, 1999)

Funders 0

None

BibTeX

@article{Creignou_1999, title={Satisfiability threshold for random XOR-CNF formulas}, volume={96–97}, ISSN={0166-218X}, url={http://dx.doi.org/10.1016/s0166-218x(99)00032-3}, DOI={10.1016/s0166-218x(99)00032-3}, journal={Discrete Applied Mathematics}, publisher={Elsevier BV}, author={Creignou, Nadia and Daude, Hervé}, year={1999}, month=oct, pages={41–53} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        7
      ]
    ],
    "date-time": "2025-07-07T08:24:10Z",
    "timestamp": 1751876650551
  },
  "reference-count": 18,
  "publisher": "Elsevier BV",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1999,
            10,
            1
          ]
        ],
        "date-time": "1999-10-01T00:00:00Z",
        "timestamp": 938736000000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "https://www.elsevier.com/tdm/userlicense/1.0/"
    },
    {
      "start": {
        "date-parts": [
          [
            2013,
            7,
            17
          ]
        ],
        "date-time": "2013-07-17T00:00:00Z",
        "timestamp": 1374019200000
      },
      "content-version": "vor",
      "delay-in-days": 5038,
      "URL": "https://www.elsevier.com/open-access/userlicense/1.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1999,
        10
      ]
    ]
  },
  "DOI": "10.1016/s0166-218x(99)00032-3",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        25
      ]
    ],
    "date-time": "2002-07-25T17:35:45Z",
    "timestamp": 1027618545000
  },
  "page": "41-53",
  "source": "Crossref",
  "is-referenced-by-count": 35,
  "special_numbering": "C",
  "title": "Satisfiability threshold for random XOR-CNF formulas",
  "prefix": "10.1016",
  "volume": "96-97",
  "author": [
    {
      "given": "Nadia",
      "family": "Creignou",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Herv\u00e9",
      "family": "Daude",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "78",
  "reference": [
    {
      "issue": "3",
      "key": "10.1016/S0166-218X(99)00032-3_BIB1",
      "doi-asserted-by": "crossref",
      "first-page": "121",
      "DOI": "10.1016/0020-0190(79)90002-4",
      "article-title": "A linear-time algorithm for testing the truth of certain quantified boolean formulas",
      "volume": "8",
      "author": "Aspvall",
      "year": "1979",
      "journal-title": "Inform. Processing Lett."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB2",
      "unstructured": "B. Bollob\u00e1s, Random Graphs, Academic Press, New York 1985."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB3",
      "doi-asserted-by": "crossref",
      "unstructured": "V. Chv\u00e1tal, B. Reed, Mick gets some (the odds are on his side), in: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, IEEE, 1992, pp. 620\u2013627.",
      "DOI": "10.1109/SFCS.1992.267789"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB4",
      "doi-asserted-by": "crossref",
      "unstructured": "L. Comtet, Advanced Combinatorics, Reidel, Dordrecht, 1974.",
      "DOI": "10.1007/978-94-010-2196-8"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB5",
      "doi-asserted-by": "crossref",
      "unstructured": "S.A. Cook, The complexity of theorem-proving procedures, in: Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158.",
      "DOI": "10.1145/800157.805047"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB6",
      "unstructured": "J.M. Crawford, D. Auton, Experimental results on the crossover point in satisfiability problems, in: Proceedings of the 11th National Conference on Artificial Intelligence, 1993, pp. 21\u201327."
    },
    {
      "issue": "1",
      "key": "10.1016/S0166-218X(99)00032-3_BIB7",
      "doi-asserted-by": "crossref",
      "first-page": "1",
      "DOI": "10.1006/inco.1996.0016",
      "article-title": "Complexity of generalized satisfiability counting problems",
      "volume": "125",
      "author": "Creignou",
      "year": "1996",
      "journal-title": "Inform. Comput."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB8",
      "first-page": "17",
      "article-title": "On the evolution of random graphs",
      "volume": "7",
      "author": "Erd\u00f6s",
      "year": "1960",
      "journal-title": "Publ. Math. Inst. Hungar. Acad. Sci."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB9",
      "doi-asserted-by": "crossref",
      "first-page": "639",
      "DOI": "10.2307/2314805",
      "article-title": "Matrices over a finite field",
      "volume": "73",
      "author": "Fisher",
      "year": "1966",
      "journal-title": "Amer. Math. Mon."
    },
    {
      "issue": "2",
      "key": "10.1016/S0166-218X(99)00032-3_BIB10",
      "doi-asserted-by": "crossref",
      "first-page": "312",
      "DOI": "10.1006/jagm.1996.0016",
      "article-title": "Analysis of two simple heuristics on a random instance of k-SAT",
      "volume": "20",
      "author": "Frieze",
      "year": "1996",
      "journal-title": "J. Algorithms"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB11",
      "unstructured": "I.P. Gent, T. Walsh, The SAT phase transition, in: Proceedings of the 11th European Conference on Artificial Intelligence, 1994, pp. 105\u2013109."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB12",
      "doi-asserted-by": "crossref",
      "unstructured": "A. Goerdt, A threshold for unsatisfiability, in: L. Havel, V. Koubek (Eds.), Mathematical Foundations of Computer Science, Springer, Berlin, 1992, pp. 264\u2013274.",
      "DOI": "10.1007/3-540-55808-X_25"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB13",
      "doi-asserted-by": "crossref",
      "unstructured": "A. Kamatah, R. Motwani, K. Palem, P. Spirakis, Tail bounds for occupancy and the satisfiability threshold conjecture, in: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994, pp. 592\u2013603.",
      "DOI": "10.1109/SFCS.1994.365732"
    },
    {
      "issue": "1",
      "key": "10.1016/S0166-218X(99)00032-3_BIB14",
      "doi-asserted-by": "crossref",
      "first-page": "47",
      "DOI": "10.1137/1112005",
      "article-title": "On the limit distribution of the number of solutions of a random system of linear equations in the class of boolean functions",
      "volume": "12",
      "author": "Kovalenko",
      "year": "1967",
      "journal-title": "Theory Probab. Appl."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB15",
      "unstructured": "D. Mitchell, B. Selman, H. Levesque, Hard and easy distributions of SAT problems, in: Proceedings of the 10th National Conference on Artificial Intelligence, 1992, pp. 459\u2013465."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB16",
      "unstructured": "A. R\u00e9nyi, Calcul des Probabilit\u00e9s, Dunod, Paris, 1966."
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB17",
      "doi-asserted-by": "crossref",
      "unstructured": "T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings 10th STOC, San Diego (CA, USA), Association for Computing Machinery, 1978, pp. 216\u2013226.",
      "DOI": "10.1145/800133.804350"
    },
    {
      "key": "10.1016/S0166-218X(99)00032-3_BIB18",
      "first-page": "283",
      "article-title": "Etude statistique de l'existence de solutions de probl\u00e8mes SAT, et application aux syst\u00e8mes-experts",
      "volume": "7",
      "author": "Simon",
      "year": "1986",
      "journal-title": "Compte Rendus de l'Acad\u00e9mie des Sciences de Paris, tome 302, S\u00e9r. I"
    }
  ],
  "container-title": "Discrete Applied Mathematics",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.elsevier.com/content/article/PII:S0166218X99000323?httpAccept=text/xml",
      "content-type": "text/xml",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://api.elsevier.com/content/article/PII:S0166218X99000323?httpAccept=text/plain",
      "content-type": "text/plain",
      "content-version": "vor",
      "intended-application": "text-mining"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        4,
        24
      ]
    ],
    "date-time": "2019-04-24T18:54:38Z",
    "timestamp": 1556132078000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://linkinghub.elsevier.com/retrieve/pii/S0166218X99000323"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1999,
        10
      ]
    ]
  },
  "references-count": 18,
  "alternative-id": [
    "S0166218X99000323"
  ],
  "URL": "http://dx.doi.org/10.1016/S0166-218X(99)00032-3",
  "relation": {},
  "ISSN": [
    "0166-218X"
  ],
  "subject": [],
  "container-title-short": "Discrete Applied Mathematics",
  "published": {
    "date-parts": [
      [
        1999,
        10
      ]
    ]
  }
}