Satisfying random linear equations over a commutative ring

Theodore Morrison (University of Waterloo)

A constraint satisfaction problem (CSP) consists of a set of \(n\) variables, and a set of \(m\) constraints on subsets of those variables. In our randomised CSP setting, our goal is to study the high probability properties of a randomly drawn CSP in the limit where \(n,m\) go to infinity and where \(m/n\) is fixed.

Many models of random CSPs are know to undergo transitions in satisfiability and solution space structure as the proportionality constant \(m/n\) increases. These include random equations over a finite field, where changes in satisfiability and the “clustering” of solutions occur at known threshold values of \(m/n\). We build on this work by studying random equations over a finite commutative ring. In this talk, we will show that equations over general rings can be reduced to studying local rings, and that some information about satisfiability over local rings can be recovered by studying equations over their residue fields. We will also discuss how the structure of the solution space over a ring compares to the structure of solutions over a field in terms of the “clustering” and “separation” of solutions.

This talk is based on joint work with Jane Gao.

 Overview  Program