Umeå universitets logga

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 18^th 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.