Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
复制标题
线性丢番图方程、群 CSP 和图同构
DOI：
10.1137/1.9781611974782.21
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Grohe
中科院分区：
文献类型：
--
作者：
C. Berkholz;M. Grohe
近年来，我们已经看到了几种基于“通用”数学规划或代数（Grobner基）技术的图同构问题的方法。对于其中大多数，已经建立了下限。事实上，已经证明，非同构的CFI-图对（由Cai，Furer和Immerman在1992年作为组合Weisfeiler-Leman算法的硬例子引入）不能通过这些数学算法区分。一个值得注意的例外是代数算法在外地2，其中没有下限是已知的。另一种更强的图同构测试方法是基于求解线性丢番图方程组（即整数上的线性方程组），这在多项式时间内是可能的。代数算法的下界可以在证明复杂性的框架中得到最好的证明，在这个框架中，它们可以被表述为代数证明系统的下界，例如零值证明或（更强大的）多项式演算。我们给出了这些系统的新的硬例子：在所有素域上，很难同时通过多项式演算证明区分的非同构图对的族，包括2，以及很难通过线性丢番图方程组方法区分的例子。在以前的论文中，我们观察到CFI图与我们称之为“群CSP”密切相关：约束满足问题，其中约束是在一个基本群的幂次子群的陪集上的成员检验（在经典的CFI-图的情况下为2）。我们的新例子也是基于群CSP（对于阿贝尔群），但在这里我们通过一些非群约束来扩展CSP，以获得更难的图同构实例。
In recent years, we have seen several approaches to the graph isomorphism problem based on “generic” mathematical programming or algebraic (Grobner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of non-isomorphic CFI-graphs (introduced by Cai, FUrer, and Immerman in 1992 as hard examples for the combinatorial Weisfeiler-Leman algorithm) cannot be distinguished by these mathematical algorithms. A notable exception were the algebraic algorithms over the field2, for which no lower bound was known. Another, in some way even stronger, approach to graph isomorphism testing is based on solving systems of linear Diophantine equations (that is, linear equations over the integers), which is known to be possible in polynomial time. So far, no lower bounds for this approach were known.Lower bounds for the algebraic algorithms can best be proved in the framework of proof complexity, where they can be phrased as lower bounds for algebraic proof systems such as Nullstellensatz or the (more powerful) polynomial calculus. We give new hard examples for these systems: families of pairs of non-isomorphic graphs that are hard to distinguish by polynomial calculus proofs simultaneously over all prime fields, including2, as well as examples that are hard to distinguish by the systems-of-linear-Diophantine- equations approach.In a previous paper, we observed that the CFI-graphs are closely related to what we call “group CSPs”: constraint satisfaction problems where the constraints are membership tests in some coset of a subgroup of a cartesian power of a base group (ℤ2in the case of the classical CFI-graphs). Our new examples are also based on group CSPs (for Abelian groups), but here we extend the CSPs by a few non-group constraints to obtain even harder instances for graph isomorphism.
登录
查看更多内容
DOI：
10.1137/1.9781611973402.120
发表时间：
2014-01
期刊：
--
影响因子：
--
作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
通讯作者：
R. O'Donnell;John Wright;Chenggang Wu;Yuan Zhou
影响因子：
4.7
作者：
M. Ellingham
通讯作者：
M. Ellingham
图同构与Birkhoff型定理
影响因子：
3.7
作者：
G. Tinhofer
通讯作者：
G. Tinhofer
计数逻辑中的 Sherali-Adams 松弛和不可区分性
DOI：
--
发表时间：
2012
期刊：
Information Technology Convergence and Services
影响因子：
--
作者：
Albert Atserias;Elitza N. Maneva
通讯作者：
Elitza N. Maneva
图同构多面体的 Sherali-Adams 松弛
DOI：
10.1016/j.disopt.2014.01.004
发表时间：
2011
期刊：
Discret. Optim.
影响因子：
--
作者：
P. Malkin
通讯作者：
P. Malkin