Cutting planes width and the complexity of graph isomorphism refutations

DOI10.1145/3677121MaRDI QIDQ6636618zbMATH OpenFDO

Authors Jacobo Torán, Florian Wörz

Publication date 12 November 2024

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

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

zbMATH Keywords

\(k\)-variable fragment first-order counting logiccutting planescutwidthgraph isomorphismHella's bijective pebble gamelinear programmingproof complexityWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

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

Cites work

• ``Outline of an algorithm for integer solutions to linear programs and ``An algorithm for the mixed integer problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A rank lower bound for cutting planes proofs of Ramsey's theorem
• An application of games to the completeness problem for formalized theories
• An exponential lower bound for the size of monotone real circuits
• An optimal lower bound on the number of variables for graph identification
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Boolean function complexity. Advances and frontiers.
• Communication lower bounds via critical block sensitivity
• CREW PRAM<scp>s</scp> and Decision Trees
• Cutting planes and the parameter cutwidth
• Definable ellipsoid method, sums-of-squares proofs, and the isomorphism problem
• Descriptive complexity
• Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
• Distinguishing Vertices of Random Graphs
• Edmonds polytopes and a hierarchy of combinatorial problems
• Elements of finite model theory.
• Graph isomorphism and theorems of Birkhoff type
• Graph isomorphism in quasipolynomial time (extended abstract)
• Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 1256733 (Why is no real title available?)
• scientific article; zbMATH DE number 7561762 (Why is no real title available?)
• scientific article; zbMATH DE number 3373541 (Why is no real title available?)
• scientific article; zbMATH DE number 3060762 (Why is no real title available?)
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Limitations of algebraic approaches to graph isomorphism testing
• Logical hierarchies in PTIME
• Lower bounds for resolution and cutting plane proofs and monotone computations
• Lower bounds for the polynomial calculus and the Gröbner basis algorithm
• Monotone circuit lower bounds from resolution
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• 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
• On Cutting Planes
• On representatives of subsets.
• On the complexity of cutting-plane proofs
• On the Hardness of Graph Isomorphism
• On the relative complexity of resolution refinements and cutting planes proof systems
• On the resolution complexity of graph non-isomorphism
• On the virtue of succinct proofs
• On the width of semialgebraic proofs and algorithms
• Outline of an algorithm for integer solutions to linear programs
• PEBBLE GAMES AND LINEAR EQUATIONS
• Polynomial algorithms in linear programming
• Random Graph Isomorphism
• Rank bounds and integrality gaps for cutting planes procedures
• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations of graph isomorphism polytopes
• Short proofs are narrow—resolution made simple
• The depth of resolution proofs
• The relative efficiency of propositional proof systems
• The symmetry rule in propositional logic
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Upper and lower bounds for first order expressibility

This page was built for publication: Cutting planes width and the complexity of graph isomorphism refutations

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