DOI: 10.1016/s0304-3975(01)00159-1. Lower bounds for random 3-SAT via differential equations

Lower bounds for random 3-SAT via differential equations

10.1016/s0304-3975(01)00159-1

Crossref journal-article

Elsevier BV

Theoretical Computer Science (78)

Bibliography

Achlioptas, D. (2001). Lower bounds for random 3-SAT via differential equations. Theoretical Computer Science, 265(1â2), 159â185.

Authors 1

Dimitris Achlioptas (first)

References 31 Referenced 93

D. Achlioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in: 32nd Annual ACM Symp. on Theory of Computing, Portland, OR, 2000, ACM, New York, 2000, pp. 28–37 (10.1145/335305.335309)
D. Achlioptas, J.H. Kim, M. Krivelevich, P. Tetali, Two-coloring random hypergraphs, in: RANDOM’00 Geneva, 2000, Proc. Inform., Vol. 8, Carleton Scientific, Waterloo, 2000, pp. 85–96.
D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, Rigorous results for random (2+p)-SAT, in: RALCOM ’97, Santorini, 1997, 1–13, 1997, pp.
D. Achlioptas, L. M. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, Y. Stamatiou, Random constraint satisfaction: a more accurate picture, Constraints, to appear. (10.1007/BFb0017433)
D. Achlioptas, M. Molloy, The analysis of a list-coloring algorithm on a random graph, in: 38th Annual Symp. on Foundations of Computer Science, Miami, FL, 1997, IEEE Computer Society Press, Los Alamitos, CA, 1997, pp. 204–212. (10.1109/SFCS.1997.646109)
D. Achlioptas, G.B. Sorkin, Optimal policies for greedy 3-SAT algorithms, in: 41st Annual Symp. on Foundations of Computer Science, Rodondo Beach, CA, 2000, pp. 590–600. (10.1109/SFCS.2000.892327)
10.1016/0097-3165(78)90059-6 / J. Combin. Theory Ser. A / The asymptotic number of labeled graphs with given degree sequences by Bender (1978)
10.1007/s100510051065 / European Phys. J. B / A variational description of the ground state structure in random satisfiability problems by Biroli (2000)
10.1016/S0195-6698(80)80030-8 / European J. Combin. / A probabilistic proof of an asymptotic formula for the number of labelled regular graphs by Bollobás (1980)
B. Bollobás, C. Borgs, J. Chayes, J.H. Kim, D.B. Wilson, The scaling window of the 2-SAT transition, 1999, Manuscript.
A.Z. Broder, A.M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas. in: 4th Annual ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 1993, ACM, New York, 1993, pp. 322–330.
10.1137/0215080 / SIAM J. Comput. / Probabilistic analysis of two heuristics for the 3-satisfiability problem by Chao (1986)
10.1016/0020-0255(90)90030-E / Inform. Sci. / Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem by Chao (1990)
V. Chvátal, B. Reed, Mick gets some (the odds are on his side). in: 33th Annual Symp. on Foundations of Computer Science, Pittsburgh, PA, 1992, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 620–627. (10.1109/SFCS.1992.267789)
S.A. Cook, The complexity of theorem-proving procedures, in: 3rd Annual ACM Symp. on Theory of Computing, Shaker Heights, OH, 1971, ACM, New York, 1971, pp. 151–158. (10.1145/800157.805047)
O. Dubois, L. M. Kirousis, Y. C. Stamatiou, Upper bounds to the unsatisfiability threshold of random 3-SAT formulas: results and techniques, Theoret. Comput. Sci., in press.
P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Vol. 10, Colloq. Mathematical Society János Bolyai, 1975, pp. 609–627.
W. Fernandez de la Vega, On random 2-SAT, 1992, Manuscript.
J. Franco, Results related to threshold phenomena research in satisfiability: lower bounds, Theoret. Comput. Sci. 265 (this Vol.) (2001) 147-157. (10.1016/S0304-3975(01)00158-X)
10.1016/0166-218X(83)90017-3 / Discrete Appl. Math. / Probabilistic analysis of the Davis–Putnam procedure for solving the satisfiability problem by Franco (1983)
10.1090/S0894-0347-99-00305-7 / J. Amer. Math. Soc. / Sharp thresholds of graph properties, and the k-SAT problem by Friedgut (1999)
10.1006/jagm.1996.0016 / J. Algorithms / Analysis of two simple heuristics on a random instance of k-SAT by Frieze (1996)
10.1006/jcss.1996.0081 / J. Comput. System Sci. / A threshold for unsatisfiability by Goerdt (1996)
R. Karp, M. Sipser, Maximum matchings in sparse random graphs, in: 22nd Annual Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1981, pp. 364–375. (10.1109/SFCS.1981.21)
L.M. Kirousis, Personal communication.
10.2307/3212147 / J. Appl. Probability / solutions of ordinary differential equations as limits of pure jump Markov processes by Kurtz (1970)
{'key': '10.1016/S0304-3975(01)00159-1_BIB27', 'series-title': 'Approximation of Population Processes, Society for Industrial and Applied Mathematics (SIAM)', 'author': 'Kurtz', 'year': '1981'} / Approximation of Population Processes, Society for Industrial and Applied Mathematics (SIAM) by Kurtz (1981)
10.1002/rsa.3240060204 / Random Struct. Algorithms / A critical point for random graphs with a given degree sequence by Molloy (1995)
R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky, Phase transition and search cost in the (2+p)-SAT problem, in: 4th Workshop on Physics and Computation, Boston, MA, 1996.
10.1038/22055 / Nature / Determining computational complexity from characteristic “phase transitions” by Monasson (1999)
10.1214/aoap/1177004612 / Ann. Appl. Probab. / Differential equations for random processes and random graphs by Wormald (1995)

Dates

Type	When
Created	23 years, 1 month ago (July 25, 2002, 1:15 p.m.)
Deposited	5 years, 7 months ago (Jan. 28, 2020, 6:05 a.m.)
Indexed	1 year, 2 months ago (June 16, 2024, 11:52 a.m.)
Issued	24 years, 1 month ago (Aug. 1, 2001)
Published	24 years, 1 month ago (Aug. 1, 2001)
Published Print	24 years, 1 month ago (Aug. 1, 2001)

Funders 0

None

BibTeX

@article{Achlioptas_2001, title={Lower bounds for random 3-SAT via differential equations}, volume={265}, ISSN={0304-3975}, url={http://dx.doi.org/10.1016/s0304-3975(01)00159-1}, DOI={10.1016/s0304-3975(01)00159-1}, number={1–2}, journal={Theoretical Computer Science}, publisher={Elsevier BV}, author={Achlioptas, Dimitris}, year={2001}, month=aug, pages={159–185} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2024,
        6,
        16
      ]
    ],
    "date-time": "2024-06-16T15:52:50Z",
    "timestamp": 1718553170744
  },
  "reference-count": 31,
  "publisher": "Elsevier BV",
  "issue": "1-2",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2001,
            8,
            1
          ]
        ],
        "date-time": "2001-08-01T00:00:00Z",
        "timestamp": 996624000000
      },
      "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": 4368,
      "URL": "https://www.elsevier.com/open-access/userlicense/1.0/"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        2001,
        8
      ]
    ]
  },
  "DOI": "10.1016/s0304-3975(01)00159-1",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        25
      ]
    ],
    "date-time": "2002-07-25T17:15:02Z",
    "timestamp": 1027617302000
  },
  "page": "159-185",
  "source": "Crossref",
  "is-referenced-by-count": 93,
  "title": "Lower bounds for random 3-SAT via differential equations",
  "prefix": "10.1016",
  "volume": "265",
  "author": [
    {
      "given": "Dimitris",
      "family": "Achlioptas",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "78",
  "reference": [
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB1",
      "doi-asserted-by": "crossref",
      "unstructured": "D. Achlioptas, Setting two variables at a time yields a new lower bound for random 3-SAT, in: 32nd Annual ACM Symp. on Theory of Computing, Portland, OR, 2000, ACM, New York, 2000, pp. 28\u201337",
      "DOI": "10.1145/335305.335309"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB2",
      "unstructured": "D. Achlioptas, J.H. Kim, M. Krivelevich, P. Tetali, Two-coloring random hypergraphs, in: RANDOM\u201900 Geneva, 2000, Proc. Inform., Vol. 8, Carleton Scientific, Waterloo, 2000, pp. 85\u201396."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB3",
      "unstructured": "D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, Rigorous results for random (2+p)-SAT, in: RALCOM \u201997, Santorini, 1997, 1\u201313, 1997, pp."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB4",
      "doi-asserted-by": "crossref",
      "unstructured": "D. Achlioptas, L. M. Kirousis, E. Kranakis, D. Krizanc, M. Molloy, Y. Stamatiou, Random constraint satisfaction: a more accurate picture, Constraints, to appear.",
      "DOI": "10.1007/BFb0017433"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB5",
      "doi-asserted-by": "crossref",
      "unstructured": "D. Achlioptas, M. Molloy, The analysis of a list-coloring algorithm on a random graph, in: 38th Annual Symp. on Foundations of Computer Science, Miami, FL, 1997, IEEE Computer Society Press, Los Alamitos, CA, 1997, pp. 204\u2013212.",
      "DOI": "10.1109/SFCS.1997.646109"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB6",
      "doi-asserted-by": "crossref",
      "unstructured": "D. Achlioptas, G.B. Sorkin, Optimal policies for greedy 3-SAT algorithms, in: 41st Annual Symp. on Foundations of Computer Science, Rodondo Beach, CA, 2000, pp. 590\u2013600.",
      "DOI": "10.1109/SFCS.2000.892327"
    },
    {
      "issue": "3",
      "key": "10.1016/S0304-3975(01)00159-1_BIB7",
      "doi-asserted-by": "crossref",
      "first-page": "296",
      "DOI": "10.1016/0097-3165(78)90059-6",
      "article-title": "The asymptotic number of labeled graphs with given degree sequences",
      "volume": "24",
      "author": "Bender",
      "year": "1978",
      "journal-title": "J. Combin. Theory Ser. A"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB8",
      "doi-asserted-by": "crossref",
      "first-page": "551",
      "DOI": "10.1007/s100510051065",
      "article-title": "A variational description of the ground state structure in random satisfiability problems",
      "volume": "14",
      "author": "Biroli",
      "year": "2000",
      "journal-title": "European Phys. J. B"
    },
    {
      "issue": "4",
      "key": "10.1016/S0304-3975(01)00159-1_BIB9",
      "doi-asserted-by": "crossref",
      "first-page": "311",
      "DOI": "10.1016/S0195-6698(80)80030-8",
      "article-title": "A probabilistic proof of an asymptotic formula for the number of labelled regular graphs",
      "volume": "1",
      "author": "Bollob\u00e1s",
      "year": "1980",
      "journal-title": "European J. Combin."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB10",
      "unstructured": "B. Bollob\u00e1s, C. Borgs, J. Chayes, J.H. Kim, D.B. Wilson, The scaling window of the 2-SAT transition, 1999, Manuscript."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB11",
      "unstructured": "A.Z. Broder, A.M. Frieze, E. Upfal, On the satisfiability and maximum satisfiability of random 3-CNF formulas. in: 4th Annual ACM-SIAM Symp. on Discrete Algorithms, Austin, TX, 1993, ACM, New York, 1993, pp. 322\u2013330."
    },
    {
      "issue": "4",
      "key": "10.1016/S0304-3975(01)00159-1_BIB12",
      "doi-asserted-by": "crossref",
      "first-page": "1106",
      "DOI": "10.1137/0215080",
      "article-title": "Probabilistic analysis of two heuristics for the 3-satisfiability problem",
      "volume": "15",
      "author": "Chao",
      "year": "1986",
      "journal-title": "SIAM J. Comput."
    },
    {
      "issue": "3",
      "key": "10.1016/S0304-3975(01)00159-1_BIB13",
      "doi-asserted-by": "crossref",
      "first-page": "289",
      "DOI": "10.1016/0020-0255(90)90030-E",
      "article-title": "Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem",
      "volume": "51",
      "author": "Chao",
      "year": "1990",
      "journal-title": "Inform. Sci."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB14",
      "doi-asserted-by": "crossref",
      "unstructured": "V. Chv\u00e1tal, B. Reed, Mick gets some (the odds are on his side). in: 33th Annual Symp. on Foundations of Computer Science, Pittsburgh, PA, 1992, IEEE Computer Society Press, Los Alamitos, CA, 1992, pp. 620\u2013627.",
      "DOI": "10.1109/SFCS.1992.267789"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB15",
      "doi-asserted-by": "crossref",
      "unstructured": "S.A. Cook, The complexity of theorem-proving procedures, in: 3rd Annual ACM Symp. on Theory of Computing, Shaker Heights, OH, 1971, ACM, New York, 1971, pp. 151\u2013158.",
      "DOI": "10.1145/800157.805047"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB16",
      "unstructured": "O. Dubois, L. M. Kirousis, Y. C. Stamatiou, Upper bounds to the unsatisfiability threshold of random 3-SAT formulas: results and techniques, Theoret. Comput. Sci., in press."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB17",
      "unstructured": "P. Erd\u0151s, L. Lov\u00e1sz, Problems and results on 3-chromatic hypergraphs and some related questions, Vol. 10, Colloq. Mathematical Society J\u00e1nos Bolyai, 1975, pp. 609\u2013627."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB18",
      "unstructured": "W. Fernandez de la Vega, On random 2-SAT, 1992, Manuscript."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB19",
      "doi-asserted-by": "crossref",
      "unstructured": "J. Franco, Results related to threshold phenomena research in satisfiability: lower bounds, Theoret. Comput. Sci. 265 (this Vol.) (2001) 147-157.",
      "DOI": "10.1016/S0304-3975(01)00158-X"
    },
    {
      "issue": "1",
      "key": "10.1016/S0304-3975(01)00159-1_BIB20",
      "doi-asserted-by": "crossref",
      "first-page": "77",
      "DOI": "10.1016/0166-218X(83)90017-3",
      "article-title": "Probabilistic analysis of the Davis\u2013Putnam procedure for solving the satisfiability problem",
      "volume": "5",
      "author": "Franco",
      "year": "1983",
      "journal-title": "Discrete Appl. Math."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB21",
      "doi-asserted-by": "crossref",
      "first-page": "1017",
      "DOI": "10.1090/S0894-0347-99-00305-7",
      "article-title": "Sharp thresholds of graph properties, and the k-SAT problem",
      "volume": "12",
      "author": "Friedgut",
      "year": "1999",
      "journal-title": "J. Amer. Math. Soc."
    },
    {
      "issue": "2",
      "key": "10.1016/S0304-3975(01)00159-1_BIB22",
      "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"
    },
    {
      "issue": "3",
      "key": "10.1016/S0304-3975(01)00159-1_BIB23",
      "doi-asserted-by": "crossref",
      "first-page": "469",
      "DOI": "10.1006/jcss.1996.0081",
      "article-title": "A threshold for unsatisfiability",
      "volume": "53",
      "author": "Goerdt",
      "year": "1996",
      "journal-title": "J. Comput. System Sci."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB24",
      "doi-asserted-by": "crossref",
      "unstructured": "R. Karp, M. Sipser, Maximum matchings in sparse random graphs, in: 22nd Annual Symp. on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1981, pp. 364\u2013375.",
      "DOI": "10.1109/SFCS.1981.21"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB25",
      "unstructured": "L.M. Kirousis, Personal communication."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB26",
      "doi-asserted-by": "crossref",
      "first-page": "49",
      "DOI": "10.2307/3212147",
      "article-title": "solutions of ordinary differential equations as limits of pure jump Markov processes",
      "volume": "7",
      "author": "Kurtz",
      "year": "1970",
      "journal-title": "J. Appl. Probability"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB27",
      "series-title": "Approximation of Population Processes, Society for Industrial and Applied Mathematics (SIAM)",
      "author": "Kurtz",
      "year": "1981"
    },
    {
      "issue": "2\u20133",
      "key": "10.1016/S0304-3975(01)00159-1_BIB28",
      "doi-asserted-by": "crossref",
      "first-page": "161",
      "DOI": "10.1002/rsa.3240060204",
      "article-title": "A critical point for random graphs with a given degree sequence",
      "volume": "6",
      "author": "Molloy",
      "year": "1995",
      "journal-title": "Random Struct. Algorithms"
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB29",
      "unstructured": "R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, L. Troyansky, Phase transition and search cost in the (2+p)-SAT problem, in: 4th Workshop on Physics and Computation, Boston, MA, 1996."
    },
    {
      "key": "10.1016/S0304-3975(01)00159-1_BIB30",
      "doi-asserted-by": "crossref",
      "first-page": "133",
      "DOI": "10.1038/22055",
      "article-title": "Determining computational complexity from characteristic \u201cphase transitions\u201d",
      "volume": "400 (6740)",
      "author": "Monasson",
      "year": "1999",
      "journal-title": "Nature"
    },
    {
      "issue": "4",
      "key": "10.1016/S0304-3975(01)00159-1_BIB31",
      "doi-asserted-by": "crossref",
      "first-page": "1217",
      "DOI": "10.1214/aoap/1177004612",
      "article-title": "Differential equations for random processes and random graphs",
      "volume": "5",
      "author": "Wormald",
      "year": "1995",
      "journal-title": "Ann. Appl. Probab."
    }
  ],
  "container-title": "Theoretical Computer Science",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.elsevier.com/content/article/PII:S0304397501001591?httpAccept=text/xml",
      "content-type": "text/xml",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://api.elsevier.com/content/article/PII:S0304397501001591?httpAccept=text/plain",
      "content-type": "text/plain",
      "content-version": "vor",
      "intended-application": "text-mining"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2020,
        1,
        28
      ]
    ],
    "date-time": "2020-01-28T11:05:15Z",
    "timestamp": 1580209515000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://linkinghub.elsevier.com/retrieve/pii/S0304397501001591"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2001,
        8
      ]
    ]
  },
  "references-count": 31,
  "journal-issue": {
    "issue": "1-2",
    "published-print": {
      "date-parts": [
        [
          2001,
          8
        ]
      ]
    }
  },
  "alternative-id": [
    "S0304397501001591"
  ],
  "URL": "http://dx.doi.org/10.1016/S0304-3975(01)00159-1",
  "relation": {},
  "ISSN": [
    "0304-3975"
  ],
  "subject": [],
  "container-title-short": "Theoretical Computer Science",
  "published": {
    "date-parts": [
      [
        2001,
        8
      ]
    ]
  }
}