Cutting planes width and the complexity of graph isomorphism refutations
From MaRDI portal
(Redirected from Publication:6636618)
Cutting planes width and the complexity of graph isomorphism refutations (scientific article; zbMATH DE number 7942536)
Cutting planes width and the complexity of graph isomorphism refutations (scientific article; zbMATH DE number 7942536)
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, 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 1254648 (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)
