The satisfiability threshold for random linear equations

Peter Ayre, Amin Coja-Oghlan, Pu Gao +1

Let $A$ be a random $m\times n$ matrix over the finite field $F_q$ with precisely $k$ non-zero entries per row and let $y\in F_q^m$ be a random vector chosen independently of $A$.…