Cutting planes width and the complexity of graph isomorphism refutations

Publication date: 12 November 2024

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

zbMATH Keywords

linear programming cutting planes proof complexity cutwidth graph isomorphism Weisfeiler-Leman algorithm \(k\)-variable fragment first-order counting logic Hella's bijective pebble game

Mathematics Subject Classification ID

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

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
On the complexity of cutting-plane proofs
Boolean function complexity. Advances and frontiers.
The depth of resolution proofs
Cutting planes and the parameter cutwidth
Elements of finite model theory.
Graph isomorphism and theorems of Birkhoff type
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
An exponential lower bound for the size of monotone real circuits
Logical hierarchies in PTIME
Lower bounds for the polynomial calculus and the Gröbner basis algorithm
The symmetry rule in propositional logic
Sherali-Adams relaxations of graph isomorphism polytopes
Edmonds polytopes and a hierarchy of combinatorial problems
On representatives of subsets.
On the relative complexity of resolution refinements and cutting planes proof systems
Sherali-Adams relaxations and indistinguishability in counting logics
A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
Outline of an algorithm for integer solutions to linear programs
An application of games to the completeness problem for formalized theories
Limitations of Algebraic Approaches to Graph Isomorphism Testing
PEBBLE GAMES AND LINEAR EQUATIONS
Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem
On Cutting Planes
Random Graph Isomorphism
Polynomial algorithms in linear programming
Distinguishing Vertices of Random Graphs
CREW PRAM<scp>s</scp> and Decision Trees
The relative efficiency of propositional proof systems
Lower bounds for resolution and cutting plane proofs and monotone computations
Short proofs are narrow—resolution made simple
Communication Lower Bounds via Critical Block Sensitivity
On the Width of Semialgebraic Proofs and Algorithms
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
On the Hardness of Graph Isomorphism
A Rank Lower Bound for Cutting Planes Proofs of Ramsey’s Theorem
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem
The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
On the Resolution Complexity of Graph Non-isomorphism
Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
Graph isomorphism in quasipolynomial time [extended abstract]
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
On the virtue of succinct proofs
Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability

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)