Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Bounds on thresholds related to maximum satisfiability of regular random formulas
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
KTH, School of Computer Science and Communication (CSC), Computational Biology, CB.
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0001-7182-9543
KTH, School of Electrical Engineering (EES), Communication Theory. KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.ORCID iD: 0000-0002-7926-5081
2010 (English)In: 6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2010, 107-111 p.Conference paper, Published paper (Refereed)
Abstract [en]

We consider the regular balanced model of satisfiability formula generation in conjunctive normal form (CNF), where each literal participates in equal number of clauses and there are k literals participating in a clause. We say that a formula is p-satisfying if there is a truth assignment satisfying 1 - 2-k + p2- fraction of clauses. Using the first moment method we determine upper bound on the threshold clause density such that there are no p-satisfying assignments with high probability above this upper bound. There are two aspects in deriving the lower bound using the second moment method. The first aspect is, given any p ∈ (0,1) and k, evaluate the lower bound on the threshold. This evaluation is numerical in nature. The second aspect is to derive the lower bound as a function of p for large enough k. We address the first aspect and evaluate the lower bound on the p-satisfying threshold using the second moment method. Based on the numerical evaluation, we observe that as k increases the ratio of the lower bound and the upper bound seems to converge to one.

Place, publisher, year, edition, pages
2010. 107-111 p.
National Category
Telecommunications
Identifiers
URN: urn:nbn:se:kth:diva-63135DOI: 10.1109/ISTC.2010.5613816Scopus ID: 2-s2.0-78649263014OAI: oai:DiVA.org:kth-63135DiVA: diva2:481680
Conference
6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). Brest. 6 September 2010 - 10 September 2010
Note
QC 20120126Available from: 2012-01-22 Created: 2012-01-22 Last updated: 2012-01-26Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Rasmussen, Lars KildehöjSkoglund, Mikael

Search in DiVA

By author/editor
Rathi, VishwambharAurell, ErikRasmussen, Lars KildehöjSkoglund, Mikael
By organisation
Communication TheoryACCESS Linnaeus CentreComputational Biology, CB
Telecommunications

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 47 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf