An algorithmic feature of a phase transition of random systems of linear equations over finite fields
Jing Shen, Yun Fan · 2012
This paper exhibits a distinguishing algorithmic feature of a phase transition point of a random system I of m linear equations over a finite field with n variables: the complexity of Gaussian elimination for testing satisfiability of the systems approaches maximum at the satisfiability threshold point m/n = 1, and the worst instances should be found at the point. It is very interesting that the algorithm exactly undergoes an easy/hard transition at the satisfiability threshold point.