Homomorphism Indistinguishability

on YouTube ↗58m

" summary

Survey of concrete claims and tools: homomorphism counts from trees coincide with indistinguishability by message‑passing GNNs; counts from cycles recover cospectrality; counts from planar graphs characterize quantum isomorphism via quantum permutation matrices commuting with adjacency. Proof tools include labeled and bilabeled graphs producing homomorphism vectors, matrix operations (trace, products), and CFI constructions with weak automorphisms to separate classes. Complexity: bounded treewidth minors → randomized polytime, bounded pathwidth → NC, planar → undecidable.

AI-written summary · about

" chapters (10)

1. 0:00Homomorphism indistinguishability intro
2. 1:09What homomorphism indistinguishability measures
3. 3:00Equivalence via homomorphism counts
4. 8:52Talk overview parts
5. 10:16Characterizing homomorphism indistinguishability
6. 20:33Equations and quantum isomorphism
7. 32:13Distinguishing power of graph classes
8. 45:37Closed classes by homomorphism
9. 49:36Key results summary
10. 50:17Q&A on hypergraphs

" related talks

• 48mApproximately Counting Graph HomomorphismsLeslie Ann Goldberg · The Classification Program of Counting Complexity
• 01h 22mTutorial 3: Geometric Invariant TheoryLaurent Manivel · Geometric Complexity Theory 2014
• 25mCubical Synthetic Homotopy TheoryLoïc Pujet · CPP 2020
• 18mCompleteness of an Axiomatization of Graph Isomorphism via Graph Rewriting in CoqChristian Doczkal · CPP 2020
• 20mPolyregular functions on unordered trees of bounded heightMikołaj Bojańczyk, Bartek Klin · POPL 2024
• 55mNon-commutative ComputationAvi Wigderson · Neo-Classical Methods in Discrete Analysis 2013
• 47mIsomorph-Free Generation Of Combinatorial Objects With Sat Modulo SymmetriesStefan Szeider, Katalin Fazekas, Markus Kirchweger, Tomas Peitl, Manfred Scheucher · Satisfiability: Theory, Practice, and Beyond 2023
• 40mHigher Inductive Types in Homotopy Type TheoryKristina Sojakova · Typelevel Summit Philadelphia 2019