Sherali-Adams relaxations and indistinguishability in counting logics

DOI10.1145/2090236.2090265zbMath1347.68175OpenAlexW2149067455MaRDI QIDQ2826069

Elitza Maneva, Albert Atserias

Publication date: 7 October 2016

Published in: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (Search for Journal in Brave)

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

zbMATH Keywords

linear programminggraph isomorphismWeisfeiler-Lehman algorithmlift-and-projectpebble gamescounting logicsSherali-Adams relaxations

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Descriptive complexity and finite models (68Q19)

Related Items (2)

The QAP-polytope and the graph isomorphism problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• The reproducible properties of correct forecasts
• The dimensions of individual strings and sequences
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• The Complexity of Forecast Testing
• The Well-Calibrated Bayesian
• Asymptotic calibration
• Dimension in Complexity Classes
• Universal prediction
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES

This page was built for publication: Sherali-Adams relaxations and indistinguishability in counting logics