The k-XORSAT threshold revisited
classification
🧮 math.CO
cs.DM
keywords
thresholdproofrandomxorsatargumentsayrecoja-oghlancombinatorica
read the original 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\"uller: Combinatorica 2020]. The proof combines physics-inspired message passing arguments with a surgical moment computation.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.