Sherali-Adams relaxations and indistinguishability in counting logics

DOI10.1145/2090236.2090265MaRDI QIDQ2826069zbMATH OpenOpenAlexFDO

Authors Albert Atserias, Elitza Maneva

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

counting logicsgraph isomorphismlift-and-projectlinear programmingpebble gamesSherali-Adams relaxationsWeisfeiler-Lehman algorithm

Mathematics Subject Classification ID

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

Recommendations

• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations of graph isomorphism polytopes
• PEBBLE GAMES AND LINEAR EQUATIONS
• Pebble games and linear equations
• Lov\'asz Meets Weisfeiler and Leman

Cites work

• Asymptotic calibration
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• scientific article; zbMATH DE number 3227613 (Why is no real title available?)
• The Complexity of Forecast Testing
• The dimensions of individual strings and sequences
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• The reproducible properties of correct forecasts
• The Well-Calibrated Bayesian
• Universal prediction

Cited in

(7)

• The QAP-polytope and the graph isomorphism problem
• Sherali-Adams relaxations of graph isomorphism polytopes
• Sherali-Adams relaxations and indistinguishability in counting logics
• A finite-model-theoretic view on propositional proof complexity
• Pebble games and linear equations
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• An algorithmic meta theorem for homomorphism indistinguishability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826069)