Cohomology in constraint satisfaction and structure isomorphism

DOI10.4230/LIPICS.MFCS.2022.75MaRDI QIDQ6584080zbMATH OpenFDO

Authors Adam Ó Conghaile

Publication date 6 August 2024

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2022.75

zbMATH Keywords

cohomologyconstraint satisfaction problemsdescriptive complexityfinite model theoryrank logicWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(6)

• Promise and infinite-domain constraint satisfaction
• Approximate graph coloring and the crystal with a hollow shadow
• Local consistency as a reduction between constraint satisfaction problems
• Semidefinite programming and linear equations vs. homomorphism problems
• Hierarchies of minion tests for PCSPs through tensors
• Limitations of affine integer relaxations for solving constraint satisfaction problems

This page was built for publication: Cohomology in constraint satisfaction and structure isomorphism

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