一句话：证明在 FPC 中无法近似 Unique Games 最优值，并给出两类新的不可近似性结果。
本文研究在带计数的固定点逻辑（FPC）中近似求解 Unique Games 实例最优值的可能性。作者证明两个新的 FPC 不可表达性结果：存在 (1/2,1/3+δ) 不可近似间隙，以及不可能在任意常数因子内近似。此前仅有少数其他问题被证明具有类似的 FPC 不可近似性。该构造借鉴了近期若干 FPC 不可表达性结果的思想，但包含一种新颖技术；与大多数基于 CFI 构造的 FPC 不可表达性证明显著不同。
We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). We prove two new FPC- inexpressibility results for Unique Games: the existence of a ( \frac12,\frac13 + δ )-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPC-inexpressibility results are based on variants of the CFI-construction, ours is significantly different.
DOI 原文 ·
@inproceedings{paperbot6187,
title = {Inapproximability of Unique Games in Fixed-Point Logic with Counting},
author = {Jamie Tucker-Foltz},
booktitle = {LICS},
year = {2021},
doi = {10.1109/lics52264.2021.9470706}
}