Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

DOI10.1137/1.9781611974782.21zbMATH Open1410.68153arXiv1607.04287OpenAlexW2516889374MaRDI QIDQ4575758FDOQ4575758

Authors: Christoph Berkholz, Martin Grohe 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In recent years, we have seen several approaches to the graph isomorphism problem based on "generic" mathematical programming or algebraic (Gr"obner basis) techniques. For most of these, lower bounds have been established. In fact, it has been shown that the pairs of nonisomorphic CFI-graphs (introduced by Cai, F"urer, 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 field GF(2), 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, including GF(2), 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 (Z_2 in 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.

Full work available at URL: https://arxiv.org/abs/1607.04287

Recommendations

• Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture
• Mathematical Foundations of Computer Science 2004
• The complexity of equivalence and isomorphism of systems of equations over finite groups
• The complexity of solving equations over finite groups
• scientific article; zbMATH DE number 66500
• The complexity of the equation solvability and equivalence problems over finite groups
• Linear time algorithms for Abelian group isomorphism and related problems
• The complexity of the equation solvability problem over semipattern groups
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Infinite Abelian Groups and Solving Systems of Linear Diophantine Equations
• Semigroup ideals and linear Diophantine equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linear Diophantine equations (11D04)

Cited In (5)

• Limitations of algebraic approaches to graph isomorphism testing
• Quantum and non-signalling graph isomorphisms
• A finite-model-theoretic view on propositional proof complexity
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Approximate graph colouring and the hollow shadow

This page was built for publication: Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575758)