Finite size scaling of random XORSAT

We consider a "configuration model" for random XORSAT which is a random system of $n$ equations over $m$ variables in $\mathbb F_2$. Each equation is of the form $y_1 + y_2 + \cdots + y_k = b$ where $k \geq 3$ is fixed, $y_1, y_2, \cdots$ are variables (not necessarily distinct) and $b \in \mathbb F_2$. The equations are chosen independently and uniformly at random with replacement. It is known \cite{Dubois02, Dietzfelbinger10, pittel2016} that there exists $ρ_k$ such that $m / n = ρ_k$ is a sharp threshold for the satisfiability of this system. In this note we show that for the configuration model, the width of SAT-UNSAT transition window for random $k$-XORSAT is $Θ(n^{-1/2})$ and also derive the exact scaling function.

No reviews yet.

No comments yet.