The Complexity of Homomorphism Indistinguishability

DOI10.4230/LIPIcs.MFCS.2019.54OpenAlexW2970918966MaRDI QIDQ5092416

Jan Böker, Gaurav Rattan, Martin Grohe, Yijia Chen

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.54

zbMATH Keywords

treewidthcounting complexitygraph homomorphism numbers

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of counting homomorphisms seen from the other side
• Some observations on the connection between counting and recursion
• Which graphs are determined by their spectrum?
• Approximate Graph Isomorphism
• PP is as Hard as the Polynomial-Time Hierarchy
• Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
• Lov\'asz Meets Weisfeiler and Leman
• Spectrally Robust Graph Isomorphism
• Graph Similarity and Approximate Isomorphism
• Graph isomorphism in quasipolynomial time [extended abstract]
• Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
• Operations with structures