Bounds on Threshold of Regular Random k-SAT View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Vishwambhar Rathi , Erik Aurell , Lars Rasmussen , Mikael Skoglund

ABSTRACT

We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. in [6]. In [6], it was shown that the threshold for regular random 2-SAT is equal to unity. Also, upper and lower bound on the threshold for regular random 3-SAT were derived. Using the first moment method, we derive an upper bound on the threshold for regular random k-SAT for any k ≥ 3 and show that for large k the threshold is upper bounded by 2k ln (2). We also derive upper bounds on the threshold for Not-All-Equal (NAE) satisfiability for k ≥ 3 and show that for large k, the NAE-satisfiability threshold is upper bounded by 2k − 1 ln (2). For both satisfiability and NAE-satisfiability, the obtained upper bound matches with the corresponding bound for the uniform model of formula generation [9,1]. For the uniform model, in a series of break through papers Achlioptas, Moore, and Peres showed that a careful application of the second moment method yields a significantly better lower bound on threshold as compared to any rigorously proven algorithmic bound [3,1]. The second moment method shows the existence of a satisfying assignment with uniform positive probability (w.u.p.p.). Thanks to the result of Friedgut for uniform model [10], existence of a satisfying assignment w.u.p.p. translates to existence of a satisfying assignment with high probability (w.h.p.). Thus, the second moment method gives a lower bound on the threshold. As there is no known Friedgut type result for regular random model, we assume that for regular random model existence of a satisfying assignments w.u.p.p. translates to existence of a satisfying assignments w.h.p. We derive the second moment of the number of satisfying assignments for regular random k-SAT for k ≥ 3. There are two aspects in deriving the lower bound using the second moment method. The first aspect is given any k, numerically evaluate the lower bound on the threshold. The second aspect is to derive the lower bound as a function of k for large enough k. We address the first aspect and evaluate the lower bound on threshold. The numerical evaluation suggests that as k increases the obtained lower bound on the satisfiability threshold of a regular random formula converges to the lower bound obtained for the uniform model. Similarly, we obtain lower bounds on the NAE-satisfiability threshold of the regular random formulas and observe that the obtained lower bound seems to converge to the corresponding lower bound for the uniform model as k increases. More... »

PAGES

264-277

Book

TITLE

Theory and Applications of Satisfiability Testing – SAT 2010

ISBN

978-3-642-14185-0
978-3-642-14186-7

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14186-7_22

DOI

http://dx.doi.org/10.1007/978-3-642-14186-7_22

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1015860978


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Linnaeus Centre ACCESS, KTH-Royal Institute of Technology, Stockholm, Sweden", 
            "School of Electrical Engineering, KTH-Royal Institute of Technology, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rathi", 
        "givenName": "Vishwambhar", 
        "id": "sg:person.016501462673.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016501462673.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Linnaeus Centre ACCESS, KTH-Royal Institute of Technology, Stockholm, Sweden", 
            "Dept. Information and Computer Science, TKK-Helsinki University of Technology, Espoo, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Aurell", 
        "givenName": "Erik", 
        "id": "sg:person.01104576776.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104576776.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Linnaeus Centre ACCESS, KTH-Royal Institute of Technology, Stockholm, Sweden", 
            "School of Electrical Engineering, KTH-Royal Institute of Technology, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rasmussen", 
        "givenName": "Lars", 
        "id": "sg:person.013557637315.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013557637315.12"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Royal Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.5037.1", 
          "name": [
            "KTH Linnaeus Centre ACCESS, KTH-Royal Institute of Technology, Stockholm, Sweden", 
            "School of Electrical Engineering, KTH-Royal Institute of Technology, Stockholm, Sweden"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Skoglund", 
        "givenName": "Mikael", 
        "id": "sg:person.015652253253.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015652253253.95"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/0166-218x(83)90017-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007285462"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(83)90017-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007285462"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(94)00133-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016436538"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0894-0347-04-00464-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027215787"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0097-3165(83)90062-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045508902"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.2006.880065", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061651089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539703434231", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879475"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/isit.2005.1523289", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095505616"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511801655", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098667872"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511791338", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098791181"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. in [6]. In [6], it was shown that the threshold for regular random 2-SAT is equal to unity. Also, upper and lower bound on the threshold for regular random 3-SAT were derived. Using the first moment method, we derive an upper bound on the threshold for regular random k-SAT for any k \u2265 3 and show that for large k the threshold is upper bounded by 2k ln (2). We also derive upper bounds on the threshold for Not-All-Equal (NAE) satisfiability for k \u2265 3 and show that for large k, the NAE-satisfiability threshold is upper bounded by 2k \u2212 1 ln (2). For both satisfiability and NAE-satisfiability, the obtained upper bound matches with the corresponding bound for the uniform model of formula generation [9,1]. For the uniform model, in a series of break through papers Achlioptas, Moore, and Peres showed that a careful application of the second moment method yields a significantly better lower bound on threshold as compared to any rigorously proven algorithmic bound [3,1]. The second moment method shows the existence of a satisfying assignment with uniform positive probability (w.u.p.p.). Thanks to the result of Friedgut for uniform model [10], existence of a satisfying assignment w.u.p.p. translates to existence of a satisfying assignment with high probability (w.h.p.). Thus, the second moment method gives a lower bound on the threshold. As there is no known Friedgut type result for regular random model, we assume that for regular random model existence of a satisfying assignments w.u.p.p. translates to existence of a satisfying assignments w.h.p. We derive the second moment of the number of satisfying assignments for regular random k-SAT for k \u2265 3. There are two aspects in deriving the lower bound using the second moment method. The first aspect is given any k, numerically evaluate the lower bound on the threshold. The second aspect is to derive the lower bound as a function of k for large enough k. We address the first aspect and evaluate the lower bound on threshold. The numerical evaluation suggests that as k increases the obtained lower bound on the satisfiability threshold of a regular random formula converges to the lower bound obtained for the uniform model. Similarly, we obtain lower bounds on the NAE-satisfiability threshold of the regular random formulas and observe that the obtained lower bound seems to converge to the corresponding lower bound for the uniform model as k increases.", 
    "editor": [
      {
        "familyName": "Strichman", 
        "givenName": "Ofer", 
        "type": "Person"
      }, 
      {
        "familyName": "Szeider", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14186-7_22", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14185-0", 
        "978-3-642-14186-7"
      ], 
      "name": "Theory and Applications of Satisfiability Testing \u2013 SAT 2010", 
      "type": "Book"
    }, 
    "name": "Bounds on Threshold of Regular Random k-SAT", 
    "pagination": "264-277", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1015860978"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14186-7_22"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "4b92ff737f3b0a161ea34785c0203552c00d48a90140b185b7ffb0f06ffb9979"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14186-7_22", 
      "https://app.dimensions.ai/details/publication/pub.1015860978"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:04", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000359_0000000359/records_29216_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-14186-7_22"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14186-7_22'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14186-7_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14186-7_22'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14186-7_22'


 

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14186-7_22 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N9e3590b96e8b43fba551eab25b9b094f
4 schema:citation https://doi.org/10.1016/0012-365x(94)00133-4
5 https://doi.org/10.1016/0097-3165(83)90062-6
6 https://doi.org/10.1016/0166-218x(83)90017-3
7 https://doi.org/10.1017/cbo9780511791338
8 https://doi.org/10.1017/cbo9780511801655
9 https://doi.org/10.1090/s0894-0347-04-00464-3
10 https://doi.org/10.1109/isit.2005.1523289
11 https://doi.org/10.1109/tit.2006.880065
12 https://doi.org/10.1137/s0097539703434231
13 schema:datePublished 2010
14 schema:datePublishedReg 2010-01-01
15 schema:description We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. in [6]. In [6], it was shown that the threshold for regular random 2-SAT is equal to unity. Also, upper and lower bound on the threshold for regular random 3-SAT were derived. Using the first moment method, we derive an upper bound on the threshold for regular random k-SAT for any k ≥ 3 and show that for large k the threshold is upper bounded by 2k ln (2). We also derive upper bounds on the threshold for Not-All-Equal (NAE) satisfiability for k ≥ 3 and show that for large k, the NAE-satisfiability threshold is upper bounded by 2k − 1 ln (2). For both satisfiability and NAE-satisfiability, the obtained upper bound matches with the corresponding bound for the uniform model of formula generation [9,1]. For the uniform model, in a series of break through papers Achlioptas, Moore, and Peres showed that a careful application of the second moment method yields a significantly better lower bound on threshold as compared to any rigorously proven algorithmic bound [3,1]. The second moment method shows the existence of a satisfying assignment with uniform positive probability (w.u.p.p.). Thanks to the result of Friedgut for uniform model [10], existence of a satisfying assignment w.u.p.p. translates to existence of a satisfying assignment with high probability (w.h.p.). Thus, the second moment method gives a lower bound on the threshold. As there is no known Friedgut type result for regular random model, we assume that for regular random model existence of a satisfying assignments w.u.p.p. translates to existence of a satisfying assignments w.h.p. We derive the second moment of the number of satisfying assignments for regular random k-SAT for k ≥ 3. There are two aspects in deriving the lower bound using the second moment method. The first aspect is given any k, numerically evaluate the lower bound on the threshold. The second aspect is to derive the lower bound as a function of k for large enough k. We address the first aspect and evaluate the lower bound on threshold. The numerical evaluation suggests that as k increases the obtained lower bound on the satisfiability threshold of a regular random formula converges to the lower bound obtained for the uniform model. Similarly, we obtain lower bounds on the NAE-satisfiability threshold of the regular random formulas and observe that the obtained lower bound seems to converge to the corresponding lower bound for the uniform model as k increases.
16 schema:editor Na3967cf0982843ba96f1d46500b4040c
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N450733e9cac24022919b2bf03b4abc0e
21 schema:name Bounds on Threshold of Regular Random k-SAT
22 schema:pagination 264-277
23 schema:productId N0dd3177ff2b14871b99603762516dd58
24 Nce3441948b034546882c2ee601c8b3a8
25 Ne0eb546128834bc5a2416ceba659cb4f
26 schema:publisher N9187505d71ab4daaa96dc340284033b1
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015860978
28 https://doi.org/10.1007/978-3-642-14186-7_22
29 schema:sdDatePublished 2019-04-16T08:04
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N432fa3371c8045ecaec23526a5d34ace
32 schema:url https://link.springer.com/10.1007%2F978-3-642-14186-7_22
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N07592d3a72ce4604bd2429e50f11cc0c rdf:first Nf87b4faa8f6d400fb9a8279b91119b56
37 rdf:rest rdf:nil
38 N0dd3177ff2b14871b99603762516dd58 schema:name readcube_id
39 schema:value 4b92ff737f3b0a161ea34785c0203552c00d48a90140b185b7ffb0f06ffb9979
40 rdf:type schema:PropertyValue
41 N42672d5149c04e12b6e98bc57bec40f5 rdf:first sg:person.015652253253.95
42 rdf:rest rdf:nil
43 N432fa3371c8045ecaec23526a5d34ace schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N450733e9cac24022919b2bf03b4abc0e schema:isbn 978-3-642-14185-0
46 978-3-642-14186-7
47 schema:name Theory and Applications of Satisfiability Testing – SAT 2010
48 rdf:type schema:Book
49 N5b97f64dd4e34357a5a3b76edd4fd575 rdf:first sg:person.013557637315.12
50 rdf:rest N42672d5149c04e12b6e98bc57bec40f5
51 N90a2722d37064e3fa51dd0f0472b4d8c rdf:first sg:person.01104576776.49
52 rdf:rest N5b97f64dd4e34357a5a3b76edd4fd575
53 N9187505d71ab4daaa96dc340284033b1 schema:location Berlin, Heidelberg
54 schema:name Springer Berlin Heidelberg
55 rdf:type schema:Organisation
56 N9e3590b96e8b43fba551eab25b9b094f rdf:first sg:person.016501462673.40
57 rdf:rest N90a2722d37064e3fa51dd0f0472b4d8c
58 Na3967cf0982843ba96f1d46500b4040c rdf:first Nfffaeb9b0103421785db9ddb75a7feff
59 rdf:rest N07592d3a72ce4604bd2429e50f11cc0c
60 Nce3441948b034546882c2ee601c8b3a8 schema:name dimensions_id
61 schema:value pub.1015860978
62 rdf:type schema:PropertyValue
63 Ne0eb546128834bc5a2416ceba659cb4f schema:name doi
64 schema:value 10.1007/978-3-642-14186-7_22
65 rdf:type schema:PropertyValue
66 Nf87b4faa8f6d400fb9a8279b91119b56 schema:familyName Szeider
67 schema:givenName Stefan
68 rdf:type schema:Person
69 Nfffaeb9b0103421785db9ddb75a7feff schema:familyName Strichman
70 schema:givenName Ofer
71 rdf:type schema:Person
72 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
73 schema:name Mathematical Sciences
74 rdf:type schema:DefinedTerm
75 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
76 schema:name Statistics
77 rdf:type schema:DefinedTerm
78 sg:person.01104576776.49 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
79 schema:familyName Aurell
80 schema:givenName Erik
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104576776.49
82 rdf:type schema:Person
83 sg:person.013557637315.12 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
84 schema:familyName Rasmussen
85 schema:givenName Lars
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013557637315.12
87 rdf:type schema:Person
88 sg:person.015652253253.95 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
89 schema:familyName Skoglund
90 schema:givenName Mikael
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015652253253.95
92 rdf:type schema:Person
93 sg:person.016501462673.40 schema:affiliation https://www.grid.ac/institutes/grid.5037.1
94 schema:familyName Rathi
95 schema:givenName Vishwambhar
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016501462673.40
97 rdf:type schema:Person
98 https://doi.org/10.1016/0012-365x(94)00133-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016436538
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/0097-3165(83)90062-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045508902
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0166-218x(83)90017-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007285462
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1017/cbo9780511791338 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098791181
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1017/cbo9780511801655 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098667872
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1090/s0894-0347-04-00464-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027215787
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/isit.2005.1523289 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095505616
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1109/tit.2006.880065 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061651089
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1137/s0097539703434231 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879475
115 rdf:type schema:CreativeWork
116 https://www.grid.ac/institutes/grid.5037.1 schema:alternateName Royal Institute of Technology
117 schema:name Dept. Information and Computer Science, TKK-Helsinki University of Technology, Espoo, Finland
118 KTH Linnaeus Centre ACCESS, KTH-Royal Institute of Technology, Stockholm, Sweden
119 School of Electrical Engineering, KTH-Royal Institute of Technology, Stockholm, Sweden
120 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...