Cutting planes width and the complexity of graph isomorphism refutations
From MaRDI portal
Publication:6636618
DOI10.1145/3677121MaRDI QIDQ6636618FDOQ6636618
Publication date: 12 November 2024
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
linear programmingcutting planesgraph isomorphismproof complexitycutwidthWeisfeiler-Leman algorithm\(k\)-variable fragment first-order counting logicHella's bijective pebble game
Cites Work
- Graph isomorphism and theorems of Birkhoff type
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- Polynomial algorithms in linear programming
- Title not available (Why is that?)
- On the Hardness of Graph Isomorphism
- Title not available (Why is that?)
- Elements of finite model theory.
- Boolean function complexity. Advances and frontiers.
- Random Graph Isomorphism
- An application of games to the completeness problem for formalized theories
- The relative efficiency of propositional proof systems
- Lower bounds for resolution and cutting plane proofs and monotone computations
- 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
- CREW PRAM<scp>s</scp> and Decision Trees
- On the complexity of cutting-plane proofs
- Edmonds polytopes and a hierarchy of combinatorial problems
- Title not available (Why is that?)
- Short proofs are narrow—resolution made simple
- On Cutting Planes
- 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
- Title not available (Why is that?)
- Lower bounds for the polynomial calculus and the Gröbner basis algorithm
- Title not available (Why is that?)
- An exponential lower bound for the size of monotone real circuits
- On the Resolution Complexity of Graph Non-isomorphism
- Sherali-Adams relaxations and indistinguishability in counting logics
- Graph isomorphism in quasipolynomial time [extended abstract]
- Upper and lower bounds for first order expressibility
- On the relative complexity of resolution refinements and cutting planes proof systems
- The depth of resolution proofs
- Logical hierarchies in PTIME
- Cutting planes and the parameter cutwidth
- The symmetry rule in propositional logic
- Outline of an Algorithm for Integer Solutions to Linear Programs and An Algorithm for the Mixed Integer Problem
- Distinguishing Vertices of Random Graphs
- Communication Lower Bounds via Critical Block Sensitivity
- Title not available (Why is that?)
- On the Width of Semialgebraic Proofs and Algorithms
- Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
- Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
- Sherali-Adams relaxations of graph isomorphism polytopes
- PEBBLE GAMES AND LINEAR EQUATIONS
- The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- On the virtue of succinct proofs
- On representatives of subsets.
- Limitations of Algebraic Approaches to Graph Isomorphism Testing
- A Rank Lower Bound for Cutting Planes Proofs of Ramsey’s Theorem
- Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem
- 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)
