  In this paper we study a variation of the random $k$-SAT problem, called
polarized random $k$-SAT. In this model there is 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, and at the other extreme
we have the fully polarized model where $p=0$, or $1$. Here there are only two
types of clauses: clauses where all $k$ variables occur pure, and clauses where
all $k$ variables occur negated. That is, for $p=0$ we get an instance of
random monotone $k$-SAT. We show that the threshold of satisfiability does not
decrease as $p$ moves away from $\frac{1}{2}$ and thus that the satisfiability
threshold for polarized random $k$-SAT is an upper bound on the threshold for
random $k$-SAT. In fact, we conjecture that asymptotically the two thresholds
coincide.

Probability;Combinatorics