标题： 谱反驳在较大域上的半随机$k$-LIN 显示英文标题

标题： Spectral Refutations of Semirandom $k$-LIN over Larger Fields

摘要： 我们研究强反驳半随机$k$-LIN$(\mathbb{F})$实例的问题：有限域$\mathbb{F}$上的$k$-稀疏非齐次线性方程组。 对于$\mathbb{F} = \mathbb{F}_2$的情况，这是对半随机$k$-XOR 实例进行反驳的广泛研究问题，[GKM22,HKM23] 的工作建立了反驳中的运行时间和子句密度之间的紧密权衡：对于任何参数$\ell$的选择，它们提供了一个$n^{O(\ell)}$-时间算法，以证明在具有$O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2 - 1} \log n /\varepsilon^4$个约束的半随机$k$-XOR 实例中，没有赋值可以满足超过$\frac{1}{2} + \varepsilon$-分数的约束，而 [KMOW17] 的工作提供了良好的证据，表明这在 Sum-of-Squares 层次结构的下界方面是紧密的，最多相差$\mathrm{polylog}(n)$因子。 然而对于更大的域，这个问题的已知结果仅通过将问题归约到$\mathbb{F}_2$的情况来建立，这导致了当前最佳上界和下界之间存在$|{\mathbb{F}}|^{3k}$的差距。 在本文中，我们给出一个算法来反驳半随机$k$-LIN$(\mathbb{F})$实例，并且对域大小$|{\mathbb{F}}|$有“正确”的依赖关系。 对于参数$\ell$的任何选择，我们的算法以$(|{\mathbb{F}}|n)^{O(\ell)}$时间运行，并且可以强反驳具有至少$O(n) \cdot \left(\frac{|{\mathbb{F}^*}| n}{\ell}\right)^{k/2 - 1} \log(n |{\mathbb{F}^*}|) /\varepsilon^4$个约束的半随机$k$-LIN$(\mathbb{F})$实例。我们提供了有力的证据表明，对域大小$|{\mathbb{F}}|$的依赖是最佳的，通过证明一个与该阈值至多相差$\mathrm{polylog}(n |{\mathbb{F}^*}|)$因子的 Sum-of-Squares 层次结构下界。我们的结果还扩展到更一般的有限阿贝尔群的情况。 显示英文摘要

摘要： We study the problem of strongly refuting semirandom $k$-LIN$(\mathbb{F})$ instances: systems of $k$-sparse inhomogeneous linear equations over a finite field $\mathbb{F}$. For the case of $\mathbb{F} = \mathbb{F}_2$, this is the well-studied problem of refuting semirandom instances of $k$-XOR, where the works of [GKM22,HKM23] establish a tight trade-off between runtime and clause density for refutation: for any choice of a parameter $\ell$, they give an $n^{O(\ell)}$-time algorithm to certify that there is no assignment that can satisfy more than $\frac{1}{2} + \varepsilon$-fraction of constraints in a semirandom $k$-XOR instance, provided that the instance has $O(n) \cdot \left(\frac{n}{\ell}\right)^{k/2 - 1} \log n /\varepsilon^4$ constraints, and the work of [KMOW17] provides good evidence that this tight up to a $\mathrm{polylog}(n)$ factor via lower bounds for the Sum-of-Squares hierarchy. However for larger fields, the only known results for this problem are established via black-box reductions to the case of $\mathbb{F}_2$, resulting in an $|{\mathbb{F}}|^{3k}$ gap between the current best upper and lower bounds. In this paper, we give an algorithm for refuting semirandom $k$-LIN$(\mathbb{F})$ instances with the "correct" dependence on the field size $|{\mathbb{F}}|$. For any choice of a parameter $\ell$, our algorithm runs in $(|{\mathbb{F}}|n)^{O(\ell)}$-time and strongly refutes semirandom $k$-LIN$(\mathbb{F})$ instances with at least $O(n) \cdot \left(\frac{|{\mathbb{F}^*}| n}{\ell}\right)^{k/2 - 1} \log(n |{\mathbb{F}^*}|) /\varepsilon^4$ constraints. We give good evidence that this dependence on the field size $|{\mathbb{F}}|$ is optimal by proving a lower bound for the Sum-of-Squares hierarchy that matches this threshold up to a $\mathrm{polylog}(n |{\mathbb{F}^*}|)$ factor. Our results also extend to the more general case of finite Abelian groups.