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
Biased 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]

The random k-SAT problem has become one of the most studied intersection points of combinatorics, computer science and physics. The basic problem is as follows: We have a set of n boolean variables and then pick m clauses of size k uniformly at random from the set of all such clauses on our variables (we give a more detailed definition later) and then ask: is the conjunction of these clauses satisfiable?

We consider a variation of the problem where there is a bias towards variables occuring pure – i.e. variables occur negated w.p. 0<p<1/2 and pure otherwise – and study how the satisfiability threshold depends on p.

For any fixed k, we find the asymptotics of the threshold as p approaches 0 or 1/2. The former confirms numerical studies.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-147516OAI: oai:DiVA.org:umu-147516DiVA, id: diva2:1203884
Note

Detta är en omarbetad, längre version av ett manuskript som ingick i författarens licentiatavhandling. Den tidigare versionen finns i följande post:

http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-121417

This is a revised, longer version of a manuscript which was included in the licentiate thesis from the same author. The previous version can be found in the following post:

http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-121417

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: 39 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