kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bounds on thresholds related to maximum satisfiability of regular random formulas
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsteori. KTH, Skolan för elektro- och systemteknik (EES), Centra, ACCESS Linnaeus Centre.
KTH, Skolan för datavetenskap och kommunikation (CSC), Beräkningsbiologi, CB.ORCID-id: 0000-0003-4906-3603
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsteori. KTH, Skolan för elektro- och systemteknik (EES), Centra, ACCESS Linnaeus Centre.ORCID-id: 0000-0001-7182-9543
KTH, Skolan för elektro- och systemteknik (EES), Kommunikationsteori. KTH, Skolan för elektro- och systemteknik (EES), Centra, ACCESS Linnaeus Centre.ORCID-id: 0000-0002-7926-5081
2010 (Engelska)Ingår i: 6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2010, s. 107-111Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2010. s. 107-111
Nationell ämneskategori
Telekommunikation
Identifikatorer
URN: urn:nbn:se:kth:diva-63135DOI: 10.1109/ISTC.2010.5613816Scopus ID: 2-s2.0-78649263014OAI: oai:DiVA.org:kth-63135DiVA, id: diva2:481680
Konferens
6th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). Brest. 6 September 2010 - 10 September 2010
Anmärkning
QC 20120126Tillgänglig från: 2012-01-22 Skapad: 2012-01-22 Senast uppdaterad: 2024-03-18Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Aurell, ErikRasmussen, Lars KildehöjSkoglund, Mikael

Sök vidare i DiVA

Av författaren/redaktören
Rathi, VishwambharAurell, ErikRasmussen, Lars KildehöjSkoglund, Mikael
Av organisationen
KommunikationsteoriACCESS Linnaeus CentreBeräkningsbiologi, CB
Telekommunikation

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 71 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf