机器学习下界研究第 2 部分 | 通过 Monodeep Mukherjee | 2024年4月

1. ETH 下近似参数化团、CSP 等的几乎最佳时间下界 (arXiv)

作者 ： 文卡特桑·古鲁斯瓦米, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

摘要：参数化不可逼近性假说（PIH）是 PCP 定理在参数化复杂性方面的模拟，它断言，存在一个常数 ε>0，使得对于任何可计算函数 f:N→N，没有 f(k)⋅ nO(1) 时间算法可以在输入域大小为 n 的 k 变量 CSP 实例时找到满足约束的 1−ε 分数的分配。 Guruswami、Lin、Ren、Sun 和 Wu (STOC'24) 最近的一项工作在指数时间假说 (ETH) 下建立了 PIH。 在这项工作中，我们改进了 PIH 的定量方面，并证明（在 ETH 下）在常数因子内近似稀疏参数化 CSP 需要 nk1−o(1) 时间。 这立即意味着，假设 ETH，在具有 k-clique 的 n 顶点图中找到 (k/2)-clique 需要 nk1−o(1) 时间。 我们还证明了近似 k-ExactCover 和 Max k-Coverage 的几乎最佳时间下界。 我们的证明遵循之前工作的蓝图，以识别“向量结构”的 ETH-hard CSP，其可满足性可以通过适当形式的“并行”PCP 进行检查。 使用进一步的减少思想，我们保证了 CSP 中约束的附加结构。 然后，我们利用这一点基于 Reed-Muller 代码和去随机化低度测试来设计一个几乎线性大小的并行 PCP。 △