论文标题
非树立矩阵的ihara-bass公式和随机CSP的强烈反驳
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
论文作者
论文摘要
我们定义了与任何对称矩阵关联的``非折 - tracking''矩阵的新颖概念，我们证明了``Ihara-bass''类型公式。 我们使用该理论来证明对多项式时间的强烈反驳，对随机约束满意度问题进行了$ K $变量的每个约束（K-CSP）。对于由约束构建的随机k-csp实例，如果该实例包含$ n $变量和$ n^{k / 2} /ε^2 $约束，我们可以有效地计算出最佳的证书满足约束的约束。 以前，这甚至以$ k $而闻名，但是对于奇数$ k $，需要$ n^{k / 2}（\ log n）^{o（1）} /ε^2 $随机约束才能获得相同的结论。 尽管改进仅是多层次的，但它克服了这类结果的重大障碍。基于当前方法构建与K-CSP实例相关的某些矩阵的证书的强烈反驳结果是quasirandom。此类证书可以来自Feige-Ofek类型的参数，来自Grothendieck的不平等的应用，也可以来自带有跟踪参数的频谱。前两种方法需要一个联合界限，当约束数为$ o（n^{\ lceil k/2 \ rceil}）$时，当约束数为$ O（n^{k/2} \ sqrt {\ log n}）时，第三个方法是无法工作的。 我们进一步应用我们的技术来获得新的PTA，以$ n^{k / 2} /ε^2 $约束在半随机设置中的$ n^{k / 2} /ε^2 $限制为$ k $ -csp实例的新ptas查找作业，其中约束是随机的，但符号模式是对手。
We define a novel notion of ``non-backtracking'' matrix associated to any symmetric matrix, and we prove a ``Ihara-Bass'' type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfaction problems with $k$ variables per constraints (k-CSPs). For a random k-CSP instance constructed out of a constraint that is satisfied by a $p$ fraction of assignments, if the instance contains $n$ variables and $n^{k/2} / ε^2$ constraints, we can efficiently compute a certificate that the optimum satisfies at most a $p+O_k(ε)$ fraction of constraints. Previously, this was known for even $k$, but for odd $k$ one needed $n^{k/2} (\log n)^{O(1)} / ε^2$ random constraints to achieve the same conclusion. Although the improvement is only polylogarithmic, it overcomes a significant barrier to these types of results. Strong refutation results based on current approaches construct a certificate that a certain matrix associated to the k-CSP instance is quasirandom. Such certificate can come from a Feige-Ofek type argument, from an application of Grothendieck's inequality, or from a spectral bound obtained with a trace argument. The first two approaches require a union bound that cannot work when the number of constraints is $o(n^{\lceil k/2 \rceil})$ and the third one cannot work when the number of constraints is $o(n^{k/2} \sqrt{\log n})$. We further apply our techniques to obtain a new PTAS finding assignments for $k$-CSP instances with $n^{k/2} / ε^2$ constraints in the semi-random settings where the constraints are random, but the sign patterns are adversarial.
