The k-XORSAT threshold revisited

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

The k-XORSAT threshold revisited

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

Institute of Discrete Mathematics (5050)

Research output: Working paper › Preprint

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.

Original language	English
Publication status	Published - 23 Jan 2023

Keywords

math.CO
cs.DM
15B52

Fields of Expertise

Information, Communication & Computing

Access to Document

2301.09287v1Submitted manuscript, 350 KBLicence: Other

Cite this

@techreport{23572e3b0f3a43528b0bd0f356a0bf18,

title = "The k-XORSAT threshold revisited",

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.",

keywords = "math.CO, cs.DM, 15B52",

author = "Amin Coja-Oghlan and Mihyun Kang and Lena Krieg and Maurice Rolvien",

year = "2023",

month = jan,

day = "23",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - The k-XORSAT threshold revisited

AU - Coja-Oghlan, Amin

AU - Kang, Mihyun

AU - Krieg, Lena

AU - Rolvien, Maurice

PY - 2023/1/23

Y1 - 2023/1/23

N2 - 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.

AB - 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.

KW - math.CO

KW - cs.DM

KW - 15B52

M3 - Preprint

BT - The k-XORSAT threshold revisited

ER -

The k-XORSAT threshold revisited

Abstract

Keywords

Fields of Expertise

Access to Document

Fingerprint

Cite this