The rank of the random -XORSAT matrix beyond satisfiability
In the authors' words
The random -XORSAT matrix is an random matrix over that represents a random instance of the -XORSAT problem. Each row of contains precisely non-zero entries in random positions. The rows are drawn independently. The matrix is known to have full row rank for below the random -XORSAT satisfiability threshold, which is known explicitly [Dubois, Mandler~2002; Pittel, Sorkin~2016]. Motivated by a problem from quantum game theory and refining a result of Cooper, Frieze and Pegden (2019), we determine the limiting distribution of the rank of beyond the satisfiability threshold.
Main resultThe abstract does not state a limitation.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.