
































We give tolerant testers with sublinear query complexity in the adjacency-list model for Unique Games. Prior tolerant testers required structural assumptions such as expansion or clusterability. For Unique Games, the tester distinguishes instances whose optimum fraction of violated constraints is at most $\varepsilon$ from those whose optimum is at least $ρ$, for $0<\varepsilon<ρ<1$, assuming $\varepsilon\log n\lesssimρ^4$. On instances with $n$ vertices and $m$ constraints, it uses $\widetilde O(\sqrt m\,ρ^{-13/2}+nρ^{-2}/\sqrt m)$ queries. We also give a specialized tester for bipartiteness, the $Q=2$ transposition case of Unique Games. Exploiting its signed structure, the tester achieves substantially better tolerance and query-complexity guarantees than the generic Unique Games tester. Writing $λ=ρ/(1+\log(1/ρ))$, the bipartiteness tester distinguishes graphs that can be made bipartite by deleting at most an $\varepsilon$ fraction of edges from graphs in which every bipartition has at least a $ρ$ fraction of edges with both endpoints on the same side, assuming $\varepsilon\log n\lesssimλ^2$, using $\widetilde O(\sqrt m/λ^2+n/(\sqrt m\,λ))$ queries.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。