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

CREATORYuichi Yoshida
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE117827
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17760

Browse the full library · About the Tower of Babel