Back to Search
Start Over
Biased random k-SAT
- Publication Year :
- 2019
-
Abstract
- This thesis consists of the following papers.I J. Larsson, The Minimum Matching in Pseudo-dimension 0 0.The second paper lives in a more general setting. There we search for any cover of the ground set V, for general families F. Each set f ∈ F receives weight w(f) uniformly at random from [0,1]. The cost of a cover f_1,f_2,...f_m is then taken to be max_i w(f_i). This is equivalent (after a rescaling) to drawing sets from F at Poisson times, and the cost of a cover is the first time V is covered. This problem is known under a number of names, perhaps most famously the coupon collector problem. In the classical formulation, single elements of V are drawn, not sets. The classical coupon collector thus corresponds to the family F consisting of singleton sets, and we call the version allowing larger sets structured coupon collector problems. The main concern of this paper is to identify relevant properties of F that affect the covering time (i.e. minimal cost of a cover), and to provide (easily checkable) sufficient conditions for concentration of the covering time.For the third paper we narrow the scopes once more, and study the biased random k-SAT problem. The random k-SAT problem can be seen as a special case of the structured coupon collector, but a special case that has far richer structure than the generic case. The ground set is the hypercube Σ_n = {0, 1}^n, and the coupons are all the k-codimensional subcubes of Σ_n. We study a slight variation on this problem: subcubes are drawn with a constant bias towards 0, so that vertices in Σ_n with fewer 1's and more 0's are easier to cover.
- Subjects :
- Matching (graph theory)
random constraint satisfaction problem
General Mathematics
0102 computer and information sciences
Computer Science::Computational Complexity
01 natural sciences
random k-SAT
Set (abstract data type)
Combinatorics
FOS: Mathematics
Mathematics - Combinatorics
60C05
Special case
QA
Coupon collector's problem
QC
Mathematics
Discrete Mathematics
Computer Sciences
Singleton
Applied Mathematics
Probability (math.PR)
Diskret matematik
Computer Graphics and Computer-Aided Design
Datavetenskap (datalogi)
Cover (topology)
phase transition
010201 computation theory & mathematics
ombinatorial probability
Combinatorics (math.CO)
Hypercube
Constant (mathematics)
Software
Mathematics - Probability
Subjects
Details
- Language :
- English
- ISSN :
- 10982418
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....06fa60ac12246c0f91d01dce221f238e