The $k$-XORSAT Threshold Revisited

  • Amin Coja-Oghlan
  • Mihyun Kang
  • Lena Krieg
  • Maurice Rolvien

Abstract

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.

Published
2024-04-19
Article Number
P2.16