Limitations of Algebraic Approaches to Graph Isomorphism Testing

DOI10.1007/978-3-662-47672-7_13zbMath1410.68152arXiv1502.05912OpenAlexW1580847017MaRDI QIDQ3448781

Martin Grohe, Christoph Berkholz

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Lov\'asz Meets Weisfeiler and Leman, Is Polynomial Time Choiceless?, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas, Unnamed Item, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Graph isomorphism and theorems of Birkhoff type
• An optimal lower bound on the number of variables for graph identification
• Logical hierarchies in PTIME
• Sherali-Adams relaxations of graph isomorphism polytopes
• Global Optimization with Polynomials and the Problem of Moments
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Pebble Games and Linear Equations
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• On the Resolution Complexity of Graph Non-isomorphism
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Linear gaps between degrees for the polynomial calculus modulo distinct primes
• Complexity of Null- and Positivstellensatz proofs