Homomorphism Counts: Expressive Power and Query Algorithms

on YouTube ↗01h 05m

" summary

Lovász’s theorem and its database analogue anchor a view where left profile and right profile are vectors of homomorphism counts; Dvořák shows Ck-equivalence matches left profiles restricted to graphs of treewidth < k, and Weisfeiler–Leman/Cai–Fürer–Immerman tools appear throughout. Main claims: many relaxations (Ck, cospectrality) are captureable from the left but provably not from any restricted right profile; chromatic equivalence is captureable from the right but not the left; left Boolean query algorithms equal Boolean combinations of conjunctive queries, and counting over N gives no extra power over Booleans for classes closed under homomorphic equivalence (proof uses CSP dichotomy, Rossman, polynomial interpolation and explicit A′/B′ constructions).

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 0:21Homomorphism counts and Poincaré
3. 3:34Homomorphism counts concept
4. 7:30Two perspectives on homomorphism counts
5. 12:04Graph profiles: left and right
6. 16:24Lovász’s Theorem and Chaudhuri-Vardi
7. 18:57Equivalence from restricted profiles
8. 23:48Treewidth and logic result
9. 27:05Left vs right profiles for CK
10. 31:50Negative results on right profiles
11. 38:22Limitations of left profiles
12. 39:25Chromatic equivalence and right profiles
13. 41:56Query algorithms with homomorphism counts
14. 47:40Beyond natural numbers in queries
15. 51:59Boolean vs natural number queries
16. 58:02Expressive power differences summary
17. 1:00:57Q&A

" related talks

• 38mConsistency, Acyclicity, and Positive SemiringsPhokion Kolaitis · Logic and Algebra for Query Evaluation 2023
• 19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: IINofar Carmeli · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 26mCounting Subgraphs in Somewhere Dense GraphsMarco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth · ITCS 2023
• 01h 01mDatalog and Equality SaturationMax Willsey · Logic and Algebra for Query Evaluation 2023
• 35mLogical Interfaces to Data, Beyond ViewsMichael Benedikt · Logic and Algebra for Query Evaluation 2023
• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 38mThe Intensional-Extensional Problem in Probabilistic DatabasesMikael Monet · Probabilistic Circuits and Logic 2023
• 44mIntermediate Relational Algorithm DesignKirk Pruhs · Fine-Grained Complexity, Logic, and Query Evaluation 2023