pipette
ENEnglish

The rank of the random -XORSAT matrix beyond satisfiability

Amin Coja-Oghlan, Maurice Rolvien

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.