The Logic of Counting Query Answers

on YouTube ↗28m

" summary

A logic called sharp logic is defined that outputs a numeric value for a formula on a finite structure and supports casting first‑order formulas, projection, multiplication, addition and integer constants; bounded width evaluation runs in polynomial time. A dichotomy is proved for existential positive queries: fixed‑parameter tractability holds iff the query compiles to a bounded‑width sharp logic representation. An algorithm uses inclusion–exclusion to normalize, applies width minimization (computable), and relies on an independence theorem showing linear independence of homomorphism‑count vectors.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:28Query evaluation
3. 3:15Studying complexity
4. 5:33Parameterized complexity
5. 7:13Classification
6. 17:12Example
7. 18:56Width minimization
8. 24:23Open issues

" related talks

• 24mWhen Less Is More: Consequence-Finding in a Weak Theory of ArithmeticZachary Kincaid, Shaowei Zhu, Nicolas Koh · POPL 2023
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 53mDirect Access for Conjunctive Queries with NegationFlorent Capelli, Oliver Irwin · Probabilistic Circuits and Logic 2023
• 19mRamsey Quantifiers in Linear ArithmeticsPascal Bergsträßer, Moses Ganardi, Anthony W. Lin, Georg Zetzsche · POPL 2024
• 29mDirect Access for Conjunctive Queries with AggregationNofar Carmeli · Logic and Algebra for Query Evaluation 2023
• 45mProblem Solved! Using Logic Programming to Find AnswersGavin McGimpsey · RubyConf 2016
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp
• 35mApproximating Certain and Possible Answers Beyond SetsBoris Glavic · Logic and Algebra for Query Evaluation 2023