Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
Kingsley Yung · arXiv (Cornell University) · 2024
The random $k$-XORSAT problem is a random constraint satisfaction problem of $n$ Boolean variables and $m=rn$ clauses, which a random instance can be expressed as a $G\mathbb{F}(2)$ linear system of the form $Ax=b$, where $A$ is a random $m \times n$ matrix with $k$ ones per row, and $b$ is a random vector. It is known that there exist two distinct thresholds $r_{core}(k) r_{core}(k)$ the sequential local algorithms with certain local rules fail to solve the random $k$-XORSAT with high probability. They include (1) the algorithm using the Unit Clause Propagation as local rule for $k \ge 9$, and (2) the algorithms using any local rule that can calculate the exact marginal probabilities of variables in instances with factor graphs that are trees, for $k\ge 13$. The well-known Belief Propagation and Survey Propagation are included in (2). Meanwhile, the best known linear-time algorithm succeeds with high probability for $r < r_{core}(k)$. Our results support the intuition that $r_{core}(k)$ is the sharp threshold for the existence of a linear-time algorithm for random $k$-XORSAT.