The Sparse Parity Matrix

The last decade witnessed several pivotal results on random inference problems where the aim is to learn a hidden ground truth from indirect randomised observations; much of this research has been guided by statistical physics intuition. Prominent examples include the stochastic block model, low-density parity check codes or compressed sensing. In all random inference problems studied so far the posterior distribution of the ground truth given the observations appears to enjoy a key property called “strong replica symmetry”. This means that the overlap of the posterior distribution with the ground truth (basically the number of bits that can be learned correctly) concentrates on a deterministic value. Whether this is generally true has been an open question. In this paper we discover an example of an inference problem based on a very simple random matrix over that fails to exhibit strong replica symmetry. Beyond its impact on random inference problems, the random matrix model, reminiscent of the binomial Erdős-Rényi random graph, gives rise to a natural random constraint satisfaction problem related to the intensely studied random k-XORSAT problem.