Tolerant Testing for Unique Games
Yuichi Yoshida · 2026
Read Tolerant Testing for Unique Games by Yuichi Yoshida (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17760.txt.
Description
Yuichi Yoshida gives tolerant testers for Unique Games with sublinear query counts in the adjacency-list model. Earlier tolerant testers needed structural assumptions like expansion or clusterability. His tester separates instances where at most an epsilon fraction of constraints are violated from those where at least a rho fraction are, under a stated epsilon-log-n condition. It uses query counts scaling like the square root of m times powers of rho. He also gives a sharper specialized tester for bipartiteness, the two-label transposition case, exploiting its signed structure.
Catalog record
| CREATOR | Yuichi Yoshida |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 117827 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.17760