Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas

DOI10.1145/3580478OpenAlexW4317659259MaRDI QIDQ6116360

Florian Wörz, Jacobo Toran

Publication date: 18 July 2023

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3580478

zbMATH Keywords

resolutionproof complexitygraph isomorphismsymmetry rule\(k\)-variable fragment first-order logic \(\mathcal{L}_k\)Immerman's pebble gamenarrow widthSRC-1

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Short proofs for tricky formulas
• The first order definability of graphs: Upper bounds for quantifier depth
• The intractability of resolution
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Upper and lower bounds for first order expressibility
• An optimal lower bound on the number of variables for graph identification
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• The complexity of resolution with generalized symmetry rules
• Space bounds for resolution
• On the complexity of resolution with bounded conjunctions
• The symmetry rule in propositional logic
• Sherali-Adams relaxations of graph isomorphism polytopes
• A combinatorial characterization of resolution width
• Sherali--Adams Relaxations and Indistinguishability in Counting Logics
• Space Complexity in Propositional Calculus
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An application of games to the completeness problem for formalized theories
• Limitations of Algebraic Approaches to Graph Isomorphism Testing
• PEBBLE GAMES AND LINEAR EQUATIONS
• Some NP-Complete Problems Similar to Graph Isomorphism
• On Resolution with Clauses of Bounded Size
• The relative efficiency of propositional proof systems
• Short proofs are narrow—resolution made simple
• How complex are random graphs in first order logic?
• On finite rigid structures
• An exponential lower bound for individualization-refinement algorithms for graph isomorphism
• On the Resolution Complexity of Graph Non-isomorphism
• Graph isomorphism in quasipolynomial time [extended abstract]
• Constructing Hard Examples for Graph Isomorphism
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
• Random Graphs
• Theory and Applications of Satisfiability Testing
• Graph isomorphism restricted by lists
• The Weisfeiler-Leman algorithm and recognition of graph properties

This page was built for publication: Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas