๐Ÿ“–
The rank of the random $k$-XORSAT matrix beyond satisfiability
Amin Coja-Oghlan, Maurice Rolvien

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

Author / Organization:
Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

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.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title The rank of the random $k$-XORSAT matrix beyond satisfiability
Author / Organization Amin Coja-Oghlan, Maurice Rolvien
Subject & Discipline math.PR
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-273159
Original Source Link Visit Source Page on arxiv.org »