The Satisfiability Threshold for K-XOR Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909599799443456 |
|---|---|
| author | Hughes, Jared A. Helton, J. William |
| author_facet | Hughes, Jared A. Helton, J. William |
| contents | A $K$-XORGAME system corresponds to a $K$-XORSAT system with the additional restriction that the variables divide uniformly into $K$ blocks. This forms a system of $m$ equations with $K n$ unknowns over $\mathbb{Z}_2$, and a perfect strategy corresponds to a solution to these equations. Equivalently, such equations correspond to colorings of a $K$-uniform $K$-partite hypergraph. This paper proves that the satisfiability threshold of $m/n$ for $K$-XORGAME problems exists and equals the satisfiability threshold for $K$-XORSAT. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_01628 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Satisfiability Threshold for K-XOR Games Hughes, Jared A. Helton, J. William Combinatorics 05A16 (Primary) A $K$-XORGAME system corresponds to a $K$-XORSAT system with the additional restriction that the variables divide uniformly into $K$ blocks. This forms a system of $m$ equations with $K n$ unknowns over $\mathbb{Z}_2$, and a perfect strategy corresponds to a solution to these equations. Equivalently, such equations correspond to colorings of a $K$-uniform $K$-partite hypergraph. This paper proves that the satisfiability threshold of $m/n$ for $K$-XORGAME problems exists and equals the satisfiability threshold for $K$-XORSAT. |
| title | The Satisfiability Threshold for K-XOR Games |
| topic | Combinatorics 05A16 (Primary) |
| url | https://arxiv.org/abs/2505.01628 |