The rank of the random $k$-XORSAT matrix beyond satisfiability
The random $k$-XORSAT matrix is an $m\times n$ random matrix $\mathbf A$ over $\mathbb F_2$ that represents a random instance of the $k$-XORSAT problem. Each row of $\mathbf A$ contains precisely $k\geq3$ non-zero entries in random positions. The rows are drawn independently. The matrix $\mathbf A$ is known to have full row rank for $m/n$ below the random $k$-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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.26300
curl -X POST /api/v1/records/arxiv/2610.26300/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.26300/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'