机器学习下界研究第 2 部分 | 通过 Monodeep Mukherjee | 2024年4月
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 […]