Graphs and Matroids - Theodore Morrison

Title:The satisfiability threshold and solution space of random uniquely extendable CSPs

Abstract: A random constraint satisfaction problem (CSP) consists of a set of variables and a set of randomly chosen constraints. Many commonly studied CSPs are constructed by choosing constraints of a specific form. One such problem is $k$-UE-SAT, where each constraint is chosen from the set of uniquely extendable (UE) constraints. A conjecture due to Molloy and Connamacher gives an exact value for the high probability satisfiability threshold of $k$-UE-SAT problems. We make progress towards this conjecture by showing that a subclass of random CSPs with UE constraints has the conjectured satisfiability threshold. We also describe the solution space geometry for this class of CSPs, and make further conjectures about the general $k$-UE-SAT problem.This talk is based on joint work with Jane Gao.