Sherali--Adams Relaxations and Indistinguishability in Counting Logics

DOI10.1137/120867834zbMath1286.68175OpenAlexW2067297906MaRDI QIDQ2839173

Albert Atserias, Elitza Maneva

Publication date: 4 July 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2445/33855

zbMATH Keywords

linear programmingcombinatorial optimizationfirst-order logicgraph isomorphismcounting quantifiersWeisfeiler-Lehman algorithm

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Logic with extra quantifiers and operators (03C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19) Fractional graph theory, fuzzy graph theory (05C72)

Related Items (18)

Limitations of Algebraic Approaches to Graph Isomorphism Testing ⋮ Lov\'asz Meets Weisfeiler and Leman ⋮ Graph isomorphism, color refinement, and compactness ⋮ Graphs Identified by Logics with Counting ⋮ On Tinhofer’s Linear Programming Approach to Isomorphism Testing ⋮ Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem ⋮ Quantum and non-signalling graph isomorphisms ⋮ Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Weisfeiler-Leman indistinguishability of graphons ⋮ Relational linear programming ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the expressive power of linear algebra on graphs ⋮ The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs ⋮ The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs

This page was built for publication: Sherali--Adams Relaxations and Indistinguishability in Counting Logics