umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Polarized random k-SAT
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We introduce a variation of the random k-SAT problem, which we call polarized random k-SAT. In polarized random k-SAT we have a polarization parameter p, and in half of the clauses each variable occurs negated with probability p and pure otherwise, while in the other half the probabilities are interchanged. For p = 1/2 we get the classical random k-SAT model.

Of particular interest is the fully polarized model where p = 0. Here there are only two types of clauses: clauses where all k variables occur pure, and clauses where all k variables occur negated.

We show that the threshold of satisfiability does not decrease as p moves away from 1. Thus the satisfiability threshold for polarized random k-SAT is an upper bound on the threshold for the classical random k-SAT. We also conjecture that the two thresholds coincide.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-147515OAI: oai:DiVA.org:umu-147515DiVA, id: diva2:1203866
Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2018-06-09
In thesis
1. On random satisfiability and optimization problems
Open this publication in new window or tab >>On random satisfiability and optimization problems
2018 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. The generalized Mézard-Parisi conjecture states that the limit of this minimum exists and is given by the solution to a certain functional equation. This conjecture has been confirmed for q=1 and for q>1. We prove it for the last remaining case 0<q<1.

In Paper II, we study generalizations of the coupon collector problem. Versions of this problem shows up naturally in various context and has been studied since the 18th century. Our focus is on using existing methods in greater generality in a unified way, so that others can avoid ad-hoc solutions.

Papers III & IV concerns the satisfiability of random Boolean formulas. The classic model is to pick a k-CNF with m clauses on n variables uniformly at random from all such formulas. As the ratio m/n increases, the formulas undergo a sharp transition from satisfiable (w.h.p.) to unsatisfiable (w.h.p.). The critical ratio for which this occurs is called the satisfiability threshold.

We study two variations where the signs of variables in clauses are not chosen uniformly. In paper III, variables are biased towards occuring pure rather than negated. In paper IV, there are two types of clauses, with variables in them biased in opposite directions. We relate the thresholds of these models to the threshold of the classical model.

Place, publisher, year, edition, pages
Umeå: Umeå Universitet, 2018. p. 10
Series
Research report in mathematics, ISSN 1653-0810
Keywords
Random graphs, k-SAT, satisfiability, coupon collector, random cover time, threshold phenomenon, concentration of measure, combinatorial probability, perfect matching, assignment problem, local graph limit, mean-field
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-147519 (URN)978-91-7601-875-0 (ISBN)
Public defence
2018-06-01, MA121, MIT-huset, Umeå, 13:15 (English)
Opponent
Supervisors
Available from: 2018-05-09 Created: 2018-05-04 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Larsson, JoelMarkström, Klas

Search in DiVA

By author/editor
Larsson, JoelMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 84 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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