We provide a simplified proof of the random $k$-XORSAT satisfiability threshold theorem. As an extension we also determine the full rank threshold for sparse random matrices over finite fields with precisely $k$ non-zero entries per row. This complements a result from [Ayre, Coja-Oghlan, Gao, Müller, Combinatorica, 2020]. The proof combines physics-inspired message passing arguments with a surgical moment computation.
@article{10_37236_11815,
author = {Amin Coja-Oghlan and Mihyun Kang and Lena Krieg and Maurice Rolvien},
title = {The {\(k\)-XORSAT} threshold revisited},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/11815},
zbl = {1536.05409},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11815/}
}
TY - JOUR
AU - Amin Coja-Oghlan
AU - Mihyun Kang
AU - Lena Krieg
AU - Maurice Rolvien
TI - The \(k\)-XORSAT threshold revisited
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/11815/
DO - 10.37236/11815
ID - 10_37236_11815
ER -
%0 Journal Article
%A Amin Coja-Oghlan
%A Mihyun Kang
%A Lena Krieg
%A Maurice Rolvien
%T The \(k\)-XORSAT threshold revisited
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11815/
%R 10.37236/11815
%F 10_37236_11815
Amin Coja-Oghlan; Mihyun Kang; Lena Krieg; Maurice Rolvien. The \(k\)-XORSAT threshold revisited. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/11815
