The sparse parity matrix

Amin Coja-Oghlan ; Oliver Cooley ; Mihyun Kang ; Joon Lee ; Jean Bernoulli Ravelomanana

Advances in Combinatronics (2023)

Résumé

Let $\mathbf{A}$ be an $n\times n$-matrix over $\mathbb{F}_2$ whose every entry equals $1$ with probability $d/n$ independently for a fixed $d>0$. Draw a vector $\mathbf{y}$ randomly from the column space of $\mathbf{A}$. It is a simple observation that the entries of a random solution $\mathbf{x}$ to $\mathbf{A} x=\mathbf{y}$ are asymptotically pairwise independent, i.e., $\sum_{i$ for $s,t\in\mathbb{F}_2$. But what can we say about the {\em overlap} of two random solutions $\mathbf{x},\mathbf{x}'$, defined as $n^{-1}\sum_{i=1}^n\mathbf{1}\{\mathbf{x}_i=\mathbf{x}_i'\}$? We prove that for $d\mathrm{e}$ the overlap concentrates on a single deterministic value $\alpha_*(d)$. By contrast, for $d>\mathrm{e}$ the overlap concentrates on a single value once we condition on the matrix $\mathbf{A}$, while over the probability space of $\mathbf{A}$ its conditional expectation vacillates between two different values $\alpha_*(d)\alpha^*(d)$, either of which occurs with probability $1/2+o(1)$. This bifurcated non-concentration result provides an instructive contribution to both the theory of random constraint satisfaction problems and of inference problems on random structures.

Détail

Publié le : 2023-09-14