#### Cristopher Moore

Paper #: 15-03-007

A *k*-uniform, *d*-regular instance of Exact Cover is a family of *m* sets *F _{n,d,k}* = {

*S*⊆ {1, . . . ,

_{j}*n*}}, where each subset has size

*k*and each 1 ≤

*i*≤

*n*is contained in

*d*of the

*S*. It is satisfiable if there is a subset

_{j}*T*⊆ {1,…,

*n*} such that |

*T*∩

*S*| = 1 for all

_{j}*j*. Alternately, we can consider it a

*d*-regular instance of Positive 1-in-

*k*SAT, i.e., a Boolean formula with

*m*clauses and

*n*variables where each clause contains

*k*variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with

*k*> 2. Letting

we show that *F _{n,d,k}* is satisfiable with high probability if

*d*<

*d*and unsatisfiable with high probability if

^{⋆}*d*>

*d*. We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below

^{⋆}*d*to 1 −

^{⋆}*o*(1) using the small subgraph conditioning method.