The k-XORSAT threshold revisited

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

Publikation: ArbeitspapierPreprint

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.
Originalspracheenglisch
PublikationsstatusVeröffentlicht - 23 Jan. 2023

Fields of Expertise

  • Information, Communication & Computing

Fingerprint

Untersuchen Sie die Forschungsthemen von „The k-XORSAT threshold revisited“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren