PreprintarXiv licencearXiv
The rank of the random k-XORSAT matrix beyond satisfiability
Abstract
The random k-XORSAT matrix is an m× n random matrix A over 𝔽2 that represents a random instance of the k-XORSAT problem. Each row of A contains precisely k≥3 non-zero entries in random positions. The rows are drawn independently. The matrix 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 A beyond the satisfiability threshold.
Related
- Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements
- SAKI-RoPE: Score-Aware Low-Rank Key Indexing with RoPE-Aware Covariance and Random-Matrix Noise Analysis
- Markovian Random Words, a Gaussian Random Matrix Model and Beyond
- An upper bound of 4.268 for the random 3-SAT satisfiability threshold
- Satisfiability and freezing in random integer programs
BibTeX
@misc{cojaoghlan2026rank,
title = {{The rank of the random $k$-XORSAT matrix beyond satisfiability}},
author = {Amin Coja-Oghlan and Maurice Rolvien},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26300},
eprint = {2610.26300},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26300},
}
RIS
TY - UNPB
TI - The rank of the random k-XORSAT matrix beyond satisfiability
AU - Amin Coja-Oghlan
AU - Maurice Rolvien
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26300
UR - https://arxiv.org/abs/2610.26300
AB - The random k-XORSAT matrix is an m× n random matrix A over 𝔽_2 that represents a random instance of the k-XORSAT problem. Each row of A contains precisely k≥3 non-zero entries in random positions. The rows are drawn independently. The matrix 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 A beyond the satisfiability threshold.
ER -