Skip to content
Preprint

The rank of the random $k$-XORSAT matrix beyond satisfiability

Oct 2026 · 0 citations · 28 references
Mathematics Computer Science

Abstract

The random $k$-XORSAT matrix is an $m\times n$ random matrix $\mathbf A$ over $\mathbb F_2$ that represents a random instance of the $k$-XORSAT problem. Each row of $\mathbf A$ contains precisely $k\geq3$ non-zero entries in random positions. The rows are drawn independently. The matrix $\mathbf A$ is known to have full row rank for $m/n$ below the random $k$-XORSAT satisfiability threshold, which is known explicitly [Dubois, Mandler~2002; Pittel, Sorkin~2016]. Motivated by a problem from quantum game theory and refining a result of Cooper, Frieze and Pegden (2019), we determine the limiting distribution of the rank of $\mathbf A$ beyond the satisfiability threshold.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.