Satisfiability of random CSPs: Uniquely extendable and non-uniquely extendable

Abstract

Determining the satisfiability threshold lies in the centre of research in random constraint satisfaction problems. When adding random constraints one at a time to a set of $n$ variables, the system transitions from being satisfiable (SAT) to unsatisfiable (UNSAT) when the number of constraints is around some critical value $\alpha n$. The famous random CSP instances include k-SAT, k-XORSAT, graph and hypergraph colouring/independent sets, linear equations over fields, etc. Some of these lie in the class of uniquely extendable CSPs, such as k-XORSAT, and linear equations over fields, whereas k-SAT, graph colouring and independent set problems are extendable but not uniquely extendable.

It has been observed that the satisfiability thresholds $\alpha^*$ of k-XORSAT and the linear equations over finite fields coincide regardless of the order of the field. Moreover, the property of uniquely extendibility governs the solution geometry and motivated the conjecture by Connamacher and Molloy that the SAT threshold of a random uniquely extendable CSP always coincide with $\alpha^*$.

We explore this conjecture and give a partial confirmation to this conjecture. Then, we explore what happens to non-uniquely extendable CSPs, and in particular, the SAT thresholds for equations over finite rings. Equations over rings differ from the above mentioned CSPs in the sense that it is not even extendable, which provides a unique perspective for understanding what governs the behaviour of the SAT thresholds.

This talk is based on joint work with Theodore Morrison.